Computation Contest #6 Results and 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:
List of participants with their entries:
|@tonimontana||Correct number||Your code is even cleaner than mine!|
|@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.|