Computation Contest #6 Results and Solution

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:

Name	Solution found	Comment
@tonimontana	Correct number	Your code is even cleaner than mine!
@crokkon	given up	:(
@portalmine	"Calculating in fractions of a second": A larger but correct number	You 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!