Project Euler Forum

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.

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

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

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...

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

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.

Here are my solution for the same numbers: Not quite the same...

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.

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...