Computation Contest #6 [2 SBI]

in #programming2 years ago (edited)

Here you can solve interesting problems using whatever programming language you like. Also you will earn SBI and sometimes STEM by doing so.
Also you might learn new things by doing so.
The tasks will be rather hard to solve without a programmable computer and some programming skills, but if you want to add a few million numbers by hand or similar, I would still give you the reward.
↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

Rules

In order to get accepted you need to somehow attach your code.

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

Problem

Today I want to give you a problem you can't just solve with brute force. You need to simplify the problem first:

Find the smallest integer number x that satisfies the following equations:

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

Tip: The number is big! Normal integers might overflow!

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

To everyone who already participated in a past contest, come back today and try a new problem(tell me if you don't want to be tagged):

In case no one gets a result(which I doubt), I will give away the prize to the person who makes the most constructive description why the problem is too hard in your opinion.

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

@contrabourdon sponsors my contests with 2 STEEM weekly.
You can support him by using a witness vote on untersatz, so he can further support this and other contests.

Sort:
2 years ago (edited)

I am a bit late but here is my solution. The equations can written like x mod 9=-5, x mod 10=-5,
x mod 11=-5...
So we just need to look for the least common multiple of 9 10 ... 128 and subtract 5. That can be done for example by iteratively computing the lcm of 2 numbers I think . My answer is 13353756090997411579403749204440236542538872688049071995
The python code is below

def gcd(x, y):

while(y):
x, y = y, x % y

return x
a = []
for x in range(9,129):
a.append(x)
lcm=1
for x in a:
lcm=int(abs(lcm*x))//int(gcd(lcm,x))
print(lcm%x,lcm)

for x in range(9,129):
if((lcm-5)%x==x-5):
pass
else:
print("Nope")
print(lcm-5)
2 years ago (edited)

So if I'm right, one solution for all equations is x = !128/!8-5 as the right side is always 5 smaller then the divider on the right side and the equations cold be rewritten as x+5 mod d = 0 so 9 to 128 have to divide x+5. When multiplying all the dividers together, the result can be divided by all of them and is exactly 5 bigger than x.
But this obviously is not the smallest number, because many numbers from 9 to 128 are multiples (e.g. 9 and 18) so we only need to multiply with the biggest multiple below 129.
My program simply tests if x is a multiple of the divider. If it's not, it multiplies x to the divider making it a divider. This procedure is repeated with dividers from 128 to 9 downwards.

x = 1
while True:
for i in range(128, 8, -1):
if x % i == 0:
pass
else:
x *= i
break
else:
x -= 5
break

So x = 3692046484038964353473548580043636599281147520791807426559995 You distributed more than 1500 upvotes. Your next target is to reach 1750 upvotes.