The longest sum of consecutive primes that add to a prime less than 1,000,000

In Project Euler problem $50,$ the goal is to find the longest sum of consecutive primes that add to a prime less than $1,000,000.$

I have an efficient algorithm to generate a set of primes between $0$ and $N.$

My first algorithm to try this was to brute force it, but that was impossible. I tried creating a sliding window, but it took much too long to even begin to cover the problem space.

I got to some primes that were summed by $100$+ consecutive primes, but had only run about $5$-$10$% of the problem space.

I'm self-taught, with very little post-secondary education.

I'm not looking for an answer, but indeed, more for pointers as to what I should be looking for and learning about in order to solve this myself.

• I have a Sieve implementation to generate a list of primes. It's the finding the consecutive sums that is causing me problems. – Kylar Jul 26 '12 at 17:04
• Are you familiar with the concept of dynamic programming? – A.Schulz Jul 26 '12 at 17:12
• The concepts, yes. I have done very little other than some experimentation with Erlang a few years ago. – Kylar Jul 26 '12 at 17:17
• I'm surprised to hear it expressed that a 'sliding window' takes much too long to even begin to cover the problem space. Generating the primes less than $10^6$ should be nearly-instantaneous, finding the partial-sums for a sliding window likewise so, and from there - well, since you have a bound on your total sum, you have an easy upper bound on the length of such a sequence; and a quick exploration, as in Robert Israel's answer, will give a lower bound. From there the search should be easy. – Steven Stadnicki Jul 26 '12 at 17:47
• Steven: Your comment gave me the key to figure out where I was being the most inefficient. I was able to move to a linear time calculation, where I was previously re-calculating the entire window each time, by keeping a previous 0..N I was able to 'slide' much faster. If you post an answer, I'll accept it. – Kylar Jul 31 '12 at 12:58

To flesh out a comment: the key insight for speeding up this problem is that by using $O(n)$ space, the intermediate sums can be calculated in constant time each: $S_{m,n} = S_{1,n}-S_{1,(m-1)}$, so storing partial sums from $1$ to $i$ lets all other partial sums be easily computed. This removes an $O(n)$ factor from the running time and makes the problem much more tractable.

• Thanks! This was the one that got me where I needed to be. – Kylar Aug 3 '12 at 17:03

The sum of the first 536 primes is $958577$ which is prime. The sum of the first 547 primes is $1001604$. That leaves a small number of possibilities to check.

• That's great - but how did you get those? If I don't understand the methods for the calculating, I can't build on them later. – Kylar Jul 26 '12 at 17:17
• @Kylar Please clarify: are you having trouble confirming these two facts, or are you looking to understand how those are useful? – Erick Wong Jul 26 '12 at 17:33
• No, I understand how they are useful - I can look at the sum of the first N primes where 536 < N < 547 and find the one closest but less than 1M. And I have no doubt they are correct - but I want to find an efficient way to calculate them. If I just take them and solve the problem without understanding the answer, I'll be back in the same place when I go to solve later problems. – Kylar Jul 26 '12 at 17:35
• The sum of the first $n$ primes should be on the order of $n^2 \log(n)/2$, which gives you an idea of how many primes to take. In Maple, add(ithprime(i),i=1..547) takes less than .02 seconds. – Robert Israel Jul 26 '12 at 17:35
• Hum, I wonder if Maple is an allowed computer language for Project Euler... – Willie Wong Jul 26 '12 at 17:38

Small speed up hint: the prime is clearly going to be odd, so you can rule out about half of the potential sums that way.

If you're looking for the largest such sum, checking things like $2+3,5+7+11,\cdots$ is a waste of time. Structure it differently so that you spend all your time dealing with larger sums. You don't need most of the problem space.

Hopefully this isn't too much of an answer for you.

• Ok, I get that. If the list contains 2 (first N primes), the list needs to be an even number. Otherwise, it must be odd. That gets rid of 1/2 the problem space. And since I have a good idea of the amount of primes, I can make a set of sliding windows that do the calculations. I can probably answer the question, but I still think there's more learning that I need. – Kylar Jul 26 '12 at 17:49
• I solved it essentially with brute force, but with a reduced brute force along these lines. Ruling out large amounts of the problem space so that you end up with far less that you need to check, though ultimately you are just running through the remaining options. "Brute force" done like this can actually be fairly fast. – Robert Mastragostino Jul 26 '12 at 17:55
• This was super helpful as an optimization - but it was Steven Stadnicki who pointed out the real issue with my algorithm. – Kylar Jul 31 '12 at 12:59

I used the mathematica code:

list = {};
Do[
a = Sum[Prime[i], {i, k, j}];
If[900000 < a <= 1000000 && PrimeQ[a],
AppendTo[list, {k, j, a}]],
{k, 1, 1000}, {j, 1, 1000}]


and then.

Sort[list, #1[] < #2[] &].


This seems very inefficient, but it was pretty quick. I found that among the sequences of the first 1000 primes, the greatest prime sum was from 459 to 695, with a value of 999749. This is probably not what you're looking for since I don't really consider mathematica to be programming.

Btw, would it be an interesting to ask how many ways a number can be summed as the sum of consecutive primes?