Problem 320

[StatujaLeha]

Hello!

Can one verify the following output?
S(2000) mod 10**18 = 2462929609139498
S(5000) mod 10**18 = 15414831967692351
S(10000) mod 10**18 = 61690942682501005
S(15000) mod 10**18 = 138829549429286488
S(20000) mod 10**18 = 246832459609482811

Thanks.

[sfabriz]

S(2000): 2462929609139498
S(5000): 15414831967692351
S(10000): 61690942682501005
S(15000): 138829549429286488
S(20000): 246832459609482811

[StatujaLeha]

Thanks, sfabriz. Just solved it. The problem was in implementaion, not in algorithm.

[wraith]

Could you share some times and code lengths?

My current solution in Mathematica (running as I write this here) would probably take an hour to complete. It's probably the longest program I've ever written in Mathematica too. It took me a lot of time to write... probably 7 hours but it's the best I could think of.

It finds S(1000) for about 14 seconds, S(2000) for about 30, and so on.

I'm surely missing something here...

[StatujaLeha]

39 non-empty lines inluding code to generate primes and without imports in Python. Running time is about 140 seconds in Core i7 860.

[carkiller]

Hi there,

I'm so sure that my solution is correct, but still I don't get the S(1000) correctly (I get 612483945066403). I even checked the first few values in J and they fulfill what I understood as the condition.

It would be great if someone could tell me if my first numbers are correct. Did I just miss a point in the Problem?

• 10 9876543150
  11 19753086300
  12 32098765220
  13 44444444140
  14 58024690948
  75 3237037008985
  125 9223456708641

Thanks - Marco.

[wraith]

Here are my solution for the same numbers:

Code: Select all

{{10, 9876543150}, {11, 22222222100}, {12, 34567901050}, {13, 49382715779}, {14, 64197530508}, {75, 3312345654609}, {125, 9372839434369}}

Not quite the same...

[carkiller]

Thanks to your numbers, wraith, I've found the error. Programming only, algorithm worked. I just gave a silly parameter and therefore an array was cut too short.

It is much, much easier when a wrong number is known!

So, finally, I get the right answer soon. YEAH!

Marco.

[mdean]

I seem to be having an issue on this problem. I'm getting the correct answer for S(1000), but my answer is not being accepted for S(1,000,000). I've double and triple-checked my constants and created 3 extra loops to verify values used to calculate N(1,000,000). All 3 loops cleared without reporting an incorrect value. The next step is to run the verification for every value from 10 to 1,000,000. Not sure how much run-time this will add.

What are the chances the accepted answer is incorrect?

Update: Apparently, the values for i = 1,000,000 were correct. Unfortunately, the values for i = 4,239 were not. Hmm... Time to track this down...