# Computation Contest #6 Results and Solution

in #programming4 years 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
while (cur <= 128):
if(i % cur == cur-5):
# Take care of prime factors already present before the start of the iteration:
if(cur == 9):
elif(cur == 10):
elif(cur == 12):
elif(cur == 14):
elif(cur == 16):
elif(isPrime(cur)): # If the current number is a prime multiply the step with it:
print(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.

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!

Sort:

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

STEEM 0.31
TRX 0.11
JST 0.034
BTC 66765.98
ETH 3234.00
USDT 1.00
SBD 4.23