Computation Contest #6 Results and Solution

in programming •  9 days ago 

Solution

The problem of this contest was to find the smallest solution for a huge equation system containing modulos:

x mod 9 = 4
x mod 10 = 5
x mod 11 = 6
x mod 12 = 7
x mod 13 = 8
:
:
:
x mod 125 = 120
x mod 126 = 121
x mod 127 = 122
x mod 128 = 123

The result is huge. So standard brute force is not possible.
My approach was to increase the step size each iteration in a way so that it is the product of all prime factors present in numbers iterated through previously. That way the modulo of all these stays the same, but I get a huge increase in speed. Here is my code(I'm using python here because it has something like BigInteger already implemented and automatically uses it for high numbers like this):

import math

def isPrime(x):
    for i in range(x-3):
        if(x % (i+2) == 0):
            return False
    return True
def isPower(x):
    for i in range(20):
        if(i <= 1):
            continue
        if(int(2**i)/int(x) == 1):
            print("power of 2")
            return 2
        if((3**i) == x):
            print(i)
            return 3
        if((5**i) == x):
            print(i)
            return 5
        if((7**i) == x):
            print(i)
            return 7
        if((11**i) == x):
            print(i)
            return 11
    return 0
        



i = 1
cur = 9
add = 1
while (cur <= 128):
    if(i % cur == cur-5):
        # Take care of prime factors already present before the start of the iteration:
        if(cur == 9):
            add *= 9
        elif(cur == 10):
            add *= 10
        elif(cur == 12):
            add *= 2
        elif(cur == 14):
            add *= 7
        elif(cur == 16):
            add *= 4
        elif(isPrime(cur)): # If the current number is a prime multiply the step with it:
            print(cur)
            add *= cur
        elif(isPower(cur) != 0): # If the current number is direct power of a prime also multiply the with that prime. Only on these powers the number of prime factors needs to be increased if the number is not a prime.
            add *= isPower(cur)
            
        cur += 1 # Go to the next number if i mod cur = cur-5
        continue
    i += add # increase i by the step to conserve the modulo of all previous numbers.
print(i) #DONE!

This code prints:
13353756090997411579403749204440236542538872688049071995

↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

List of participants with their entries:

NameSolution foundComment
@tonimontanaCorrect numberYour code is even cleaner than mine!
@crokkongiven up:(
@portalmine"Calculating in fractions of a second": A larger but correct numberYou should take care about prime factors and not only dividers. But because you were just a small step from the correct solution I will count you as a winner.

↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

Winners:

Congratulations @portalmine (→ @portalvotes) and @tonimontana, you won 1 SBI each.

↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

The next contest starts today. Don't miss it!

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

A bonus $trendotoken tip from ONECENT!
Also consider MAPR fund and MAXUV vote bonds too.
MAP Steem FinTech: growing your STEEM without SP.