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.
↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓