Have I checked every consecutive subset of this list?

Question

I'm trying to solve problem 50 on Project Euler. Don't give me the answer or solve it for me, just try to answer this specific question.

The goal is to find the longest sum of consecutive primes that adds to a prime below one million. I wrote a sieve to find all the primes below n, and I have confirmed that it is correct. Next, I am going to check the sum of each subset of consecutive primes using the following method:

I have a empty list sums. For each prime number, I add it to each element in sums and check the new sum, then I append the prime to sums.

Here it is in python

primes = allPrimesBelow(1000000)
sums = []
for p in primes:
    for i in range(len(sums)):
        sums[i] += p
        check(sums[i])
    sums.append(p)

I want to know if I have called check() for every sum of two or more consecutive primes below one million

The problem says that there is a prime, 953, that can be written as the sum of 21 consecutive primes, but I am not finding it.

Answer 1

Your code is correct. I ran it and it does generate the number 953, so the problem is probably with your prime generating function. There should be 78498 primes below a million - you may want to check if you get that result.

That said, your code will take a long time to run, since it will call check() 3,080,928,753 times. You may want to find a method that checks less sums. I won't expand on this since you asked for no spoilers, but let me know if you're interested in general hints.

Answer 2

I don't have a straight answer off the top of my head, but have you tried making sums into a nested array and then appending primes p to the sub-arrays instead of adding them to a summation counter? That would let you visually check which primes were being added to each sub-array, and by extension would tell you which primes the original code was summing up.