Have I checked every next subset of this list?
I am trying to solve problem 50 on Project Euler . Don't give me an 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 below a million to the first. I wrote a sieve to find all the primes below n and I have confirmed that it is correct. Then I'm going to check the sum of each subset of consecutive primes using the following method:
I have an empty list sums
. For each prime number, I add it to each element in sums
and check the new sum, then add a 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 each sum two or more consecutive primes below a million
The problem is that there is a prime number 953 that can be written as the sum of 21 consecutive primes, but I can't find it.
a source to share
Your code is correct. I ran it and it generates the number 953, so the problem is probably with your main producing function. There should be 78498 primes below a million - you can check if you get a result.
However, your code will take a long time, as it will call check () 3,080,928,753 times. You can find a method that checks fewer sums. I won't expand on this because you didn't ask for spoilers, but let me know if you're interested in general hints.
a source to share
I don't have a straightforward answer head-on, but have you tried to do sums into a nested array and then add primes p to sub-arrays instead of adding them to the sum counter? This will allow you to visually check which primes are being added to each submatrix, and by extension will tell you which primes the source code sums up.
a source to share