(15 votes, average: 4.73 out of 5)
Loading...
Project Euler 50: Find the prime number, below one-million, that can be written as the sum of the most consecutive primes.
Project Euler 50 Problem Description
Project Euler 50: The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
Analysis
We need to answer two simple questions: With which prime do we start and how many consecutive primes do we need to add.
We built an array of sums, each time adding a new prime to the total until the total exceeded the maximum (1,000,000 in this case.) It is then a simple task to look at different sums and record the one with the most terms.
Project Euler 50 Solution
Runs < 0.003 seconds in Python 2.7.
Use this link to get the Project Euler 50 Solution Python 2.7 source.
Afterthoughts
- Was surprised by how many terms were required.
- Here is a good discussion for prime sums
- Table of test values
| Limit | Starting prime | Prime sum | # terms | Run time |
|---|---|---|---|---|
| 102 | 2 | 41 | 6 Terms | <0.001 sec. |
| 103 | 7 | 953 | 21 Terms | <0.001 sec. |
| 104 | 3 | 9521 | 65 Terms | <0.001 sec. |
| 105 | 3 | 92951 | 183 Terms | <0.001 sec. |
| 106 | 7 | 997651 | 543 Terms | 0.002 sec. |
| 107 | 5 | 9951191 | 1587 Terms | 0.005 sec. |
| 108 | 7 | 99819619 | 4685 Terms | 0.011 sec. |
| 109 | 11 | 999715711 | 13935 Terms | 0.03 sec. |
| 1010 | 2 | 9999419621 | 41708 Terms | 0.1 sec. |
| 1011 | 19 | 99987684473 | 125479 Terms | 0.36 sec. |
| 1012 | 5 | 999973156643 | 379317 Terms | 1 sec. |
Project Euler 50 Solution last updated
(summax that is necessary for us
Posted by Francky | April 28, 2011, 8:57 AMhow could you make sure that the answer you get must be correct?
for this case:
while (sum<max):
sum+=primes[count]
prime_sum.append(sum)
count+=1
I don't think (sum<max) is a legal condition. note that even sum exceeds max,
prime_sum[j]-prime_sum[i]
might be smaller than max, thus it could be the final answer.
Posted by jcchen | January 30, 2011, 6:44 AMI had to look at the code after so many years but confirmed that the logic is sound. Even for 100,000,000 the program produces a result of 99,819,619 with 4685 terms.
Our table of consecutive prime sums can never exceed our maximum, so sum < max is valid. Does this help at all?
Posted by Mike | February 1, 2011, 3:30 PMNo, your logic is wrong. Run your code with threshold being 997652, you would see 542 as max terms.
Posted by Quang Hoang | September 22, 2021, 1:07 AMI am re-writing these solutions and it looks like I need to revisit this one to include a fix and a HackerRank solution. Thanks
Posted by Mike Molony | December 27, 2021, 1:38 PM