Computation Contest #6 [2 SBI]

in #programming5 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

No upvote, No resteem, No follow required!

I will give the prize randomly to those who solved the problem.

If two pieces of code are to closely related I might consider the later of them as copied which results in no prize for that person.

You have 4 days to solve it.

Even though this is about computation I will also accept algebraic solutions if you find one.

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):
@crokkon @kaeserotor @tonimontana @ninahaskin

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:  

You should try to make more optimizations like the one you did for 128.

By the way: A good solution won't run more than a few minutes.

*Calculating in fractions of a second* 😂

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)

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

If I win, please send the rewards to @portalvotes

Your solution is good, but it isn't the smallest. There one which is 5 orders of magnitude smaller.

Congratulations @quantumdeveloper! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You distributed more than 1500 upvotes. Your next target is to reach 1750 upvotes.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

You can upvote this notification to help all Steem users. Learn how here!