## 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:

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

10^{2}
| 2 | 41 | 6 Terms | <0.001 sec. |

10^{3}
| 7 | 953 | 21 Terms | <0.001 sec. |

10^{4}
| 3 | 9521 | 65 Terms | <0.001 sec. |

10^{5}
| 3 | 92951 | 183 Terms | <0.001 sec. |

10^{6}
| 7 | 997651 | 543 Terms | 0.002 sec. |

10^{7}
| 5 | 9951191 | 1587 Terms | 0.005 sec. |

10^{8}
| 7 | 99819619 | 4685 Terms | 0.011 sec. |

10^{9}
| 11 | 999715711 | 13935 Terms | 0.03 sec. |

10^{10}
| 2 | 9999419621 | 41708 Terms | 0.1 sec. |

10^{11}
| 19 | 99987684473 | 125479 Terms | 0.36 sec. |

10^{12}
| 5 | 999973156643 | 379317 Terms | 1 sec. |

*Project Euler 50 Solution last updated*

(summax that is necessary for us

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

I 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?