Problem 320

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
StatujaLeha
Posts: 4
Joined: Wed Jan 12, 2011 2:08 pm

Problem 320

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
Posts: 175
Joined: Thu Apr 06, 2006 12:18 am
Location: London - UK

Re: Problem 320

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

StatujaLeha
Posts: 4
Joined: Wed Jan 12, 2011 2:08 pm

Re: Problem 320

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

wraith
Posts: 8
Joined: Thu Jul 26, 2007 10:27 pm

Re: Problem 320

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
Posts: 4
Joined: Wed Jan 12, 2011 2:08 pm

Re: Problem 320

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
Posts: 5
Joined: Mon Jan 31, 2011 12:19 pm

Re: Problem 320

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
Posts: 8
Joined: Thu Jul 26, 2007 10:27 pm

Re: Problem 320

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
Posts: 5
Joined: Mon Jan 31, 2011 12:19 pm

Re: Problem 320

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
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 320

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