Project Euler Problem #50 Consecutive Prime Sums

Question

Problem: Which prime, below one-million, can be written as the sum of the most consecutive primes?

At the moment my code runs for over 200 seconds and was wondering how I can find a way to bring that down by a large amount. I have tried optimising it as much as I can and added an extra if statement, if(subSum < 1000000): to reduce the need to see if subSum is a prime. Here is my code at the moment:

def sieve(num):
    primes = []
    import math
    for i in range(num):
        primes.append(True)
    j = 1
    while(j<(math.sqrt(num)+1)):
        k = (j+1)*2
        while(k<(num+1)):
            primes[k-1] = False
            k+=(j+1)
        j+=1
    primes[0] = False
    prime = []
    for a in range(num):
        if(primes[a] == True):
            prime.append(a+1)
    return prime

primes = sieve(1000000)
count = 1
high = 0
length = len(primes)
while count <= length: 
    i = 0
    while(i<(length-count)):
        sub = primes[i:i+count]
        subSum = sum(sub)
        if(subSum < 1000000):
            if(subSum in primes):
                if(subSum>high):
                    high = subSum
                break
            else: 
                i+=1
        else:
            break
    count += 1
print(high)

Thanks for any help.

Answer 1

I'll try to focus on the performance of the code provided, and what can be done to improve it. One key observation that I found is that it is more efficient to start searching for larger consecutive sums, and move towards shorter until we find a valid candidate.

Then the obvious question is: where do we start? To find this, simply check the cumulative sums for the first n primes. As n increases, so does the sum. When the sum is above 1000000, it would not be possible to find a sum of n primes which is in the list of primes below 1000000. With this, it can be deduced that the sum can contain 546 elements at most. You should verify this on your own.

Another observation is that 2 is the only even prime. With the knowledge that odd + odd = even, even + odd = odd + even = odd, and even + even = even, we can deduce that if and only if 2 is a part of the consecutive sum, the sum must contain an even number of elements. Thus, we must only check the very first consecutive sum (the one starting with 2) when the sum has an even number of elements.

With all of this in place, the speed of the search is improved considerably.

n = 1000000
found = False
primes = sieve(n)
primes_set = set(primes)

for test_len in range(545, 1, -2):
    for i in range(0, len(primes)-test_len):
        s = sum(primes[i:i+test_len])
        if s in primes_set:
            print("found", test_len, s)
            found = True
            break
    if found:
        break

This is of course only a small snippet, and not the full program. For example, this does not test for even length consecutive sums, but that should be trivial with the information provided above. However, the execution time for the loop is less than a second, with the majority of the runtime now being used by the prime sieve. However, optimizing that is outside the scope of this answer.

Answer 2

** This is not a full review but I will try to tackle some important points.

Import statements

def sieve(num):
    primes = []
    import math

According to pep8 https://www.python.org/dev/peps/pep-0008/ the official Python style guide: Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants, not inside a function like in the case of your sieve function.

Prime sieve

I'm not an expert of prime sieves however I guess your implementation is very inefficient therefore here's the common implementation:

def sieve(upper_bound):
    primes = [True] * upper_bound
    primes[0] = primes[1] = False

    for i, prime in enumerate(primes):
        if prime:
            yield i
            for n in range(i * i, upper_bound, i):
                primes[n] = False

You might try running your version of sieve and this one, they run in the following times when I ran the test on both on my i5 macbook pro for a 10 ** 7 input size:

Time: 18.267110993 seconds. (your version)

Time: 2.6265673870000015 seconds. (the other version)

you might want to try running the test yourself and see the results.

Functions

You use functions in programming to bundle a set of instructions that you want to use repeatedly or that, because of their complexity, are better self-contained in a sub-program and called when needed. That means that a function is a piece of code written to carry out a specified task. To carry out that specific task, the function might or might not need multiple inputs. When the task is carried out, the function can or can not return one or more values. Therefore we can enclose the following piece of code inside a function.

primes = sieve(1000000)
count = 1
high = 0
length = len(primes)
while count <= length: 
    i = 0
    while(i<(length-count)):
        sub = primes[i:i+count]
        subSum = sum(sub)
        if(subSum < 1000000):
            if(subSum in primes):
                if(subSum>high):
                    high = subSum
                break
            else: 
                i+=1
        else:
            break
    count += 1
print(high)

In the following way:

def get_longest_prime_sum(upper_bound):
    """Return sum of the longest prime sequence in range upper_bound exclusive."""
    primes = sieve(upper_bound)
    count = 1
    high = 0
    length = len(primes)
    while count <= length: 
        i = 0
        while(i<(length-count)):
            sub = primes[i:i+count]
            subSum = sum(sub)
            if(subSum < 1000000):
                if(subSum in primes):
                    if(subSum>high):
                        high = subSum
                    break
                else: 
                    i+=1
            else:
                break
        count += 1
    return high

The rest of the code:

unfortunately, I couldn't get myself to have enough patience to wait for 200 seconds to examine what the code actually does however here's a link to my own implementation to the same problem: Project Euler # 50 Consecutive prime sum in Python

Note *** this is not the most optimal solution

However it returns the right answer in almost 2 seconds, so you can examine how I implemented it and you will find a very useful review below my code, you might check it to give you some insights on other ways of solving the same problem.

Answer 3

PEP-008 Guidelines

Consult PEP-008 for style guideline for writing idiomatic Python. You can use various checkers, such as PyLint or PyFlakes to verify compliance with the PEP-008 guidelines.

Some highlight:

• if and while loops do not need parenthesis (...) around the expression. Write while k < num + 1:, instead of while(k<(num+1)).
• Use one space around operators. Ie, write j += 1 instead of j+=1.
• Testing if a value is True does not require comparison against the value True. Simply use the value itself. Ie, write if primes[a]: instead of if(primes[a] == True):
• Avoid mixedCase. Instead of subSum, use sub_sum.

Multiplying a List

This code is very inefficient:

primes = []
for i in range(num):
    primes.append(True)

With 1 million candidates in your prime sieve, you will be growing the list by 1 value 1 million times. This may translate to 1 million reallocations, and 1 million copy operations, an \$O(N^2)\$ operation since the number of elements to copy to the new list keeps increasing.

Creating a list of 1 million True values is trivial:

primes = [True] * num

Pro tip: since all but one even candidate is prime, you actually want a list of 500 thousand pairs of True, False values.

primes = [True, False] * (num // 2)
primes[0] = False                    # One isn't prime
primes[1] = True                     # But two is

... and then you can only check odd candidates in your sieve for half the work.

Don't evaluate expensive constant values in a loop

This loop:

while(j<(math.sqrt(num)+1)):
    # ...
    j += 1

will evaluate the square-root of num one thousand times!

Since num is not changing in the loop, the resulting \$\sqrt{n}\$ value won't change either. And square-roots are expensive to calculate. So instead:

limit = math.sqrt(num) + 1
while j < limit:
    # ...
    j += 1

Use for instead of while-with-increment

The loop:

j = 1
while j < limit:
    # ...
    j += 1

can easily be replaced by a for loop:

for j in range(1, limit):
    # ...

Pro-tip: Because we can initialize primes with [False, True, False, True, False, True, ... ] above, we can skip over the even candidates using a step-value in the range():

for j in range(1, limit, 2):
    # ...

List comprehension

We again encounter the inefficient \$O(N^2)\$ list.append()-in-loop code:

prime = []
for a in range(num):
    if(primes[a] == True):
        prime.append(a+1)

Here, we can't use list-multiplication to create the desired list. Instead, we can use list-comprehension:

prime = [ a + 1 for a in range(num) if primes[a] ]

Why is this better? The Python interpreter can "guess" the resulting list is no longer than num entries, and allocate sufficient space. Then, it will loop through and populate the list with the successive a + 1 values where primes[a] is true. At the end, it realizes the list is much shorter than it initially allocated, and can resize the list down to actual size.

But wait. We are looking up in primes[] successive values, which involves 1 million indexing operations. Instead of looping over a range(num), we should loop over the primes list itself. No indexing; just extracting each value from the list one after the other.

prime = [ a + 1 for a, prime in enumerate(primes) if prime ]

That +1 is annoying; that is several thousand addition operations. It would be better if we counted elements of primes beginning with 1 for the primes[0] value:

prime = [ a for a, prime in enumerate(primes, 1) if prime ]

Easy peasy.

Zero-based indexing

Your indexing scheme, which stores the primality of a in primes[a-1] is confusing, and causes more headaches than it's worth. Yes, you've saved 1 list element, but that tiny savings in memory is not worth the confusion.

Store the primality of a in primes[a].

Realizing Slices

Consider the code:

    sub = primes[i:i+count]
    subSum = sum(sub)

It takes the slice primes[i:i+count], and then assigns it to a variable. At that moment, the Python interpreter MUST copy the slice into a real list. Then, you never use sub again, after the next statement.

If you wrote:

subSum = sum(primes[i:i+count])

the Python interpreter may pass an iterator to the slice to the sum() function, and add up the numbers. The copy of the slice into a real list may be avoided.

x "in" list

To test if subSum in primes:, the interpreter checks the each element of the list to see if it matches the subSum, until either a match is found, or the end of the list is encountered. This is an \$O(N)\$ operation. Not exactly slow, but it takes time.

If you converted primes into a set beforehand, the values are hashed into bins, and the in operation drops to \$O(1)\$, which is fast.

primes = set(primes)

But ... creating the set is an \$O(N)\$ operation and you already generated a list of primality flags in sieve(). If you returned that list of flags, in addition to your list of prime numbers, your prime test could be:

if primes_flags_from_sieve[subSum-1]:

which not only is \$O(1)\$, it is just a lookup! No hashing of the value to lookup. So this would be very fast.

Algorithmic Improvements

Repeatedly adding close to the same sequence of numbers together over and over again is a waste of time:

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + ...
    3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + ...
        5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + ...
      :        :          :
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29
    3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29
        5 + 7 + 11 + 13 + 17 + 19 + 23 
      :        :          :
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 
    3 + 5 + 7 + 11 + 13 + 17 + 19 + 23
        5 + 7 + 11 + 13 + 17 + 19 + 23
      :        :          :
2 + 3 + 5 + 7 + 11 + 13 + 17 + 19
    3 + 5 + 7 + 11 + 13 + 17 + 19 
        5 + 7 + 11 + 13 + 17 + 19
      :        :          :
2 + 3 + 5 + 7 + 11 + 13 + 17
    3 + 5 + 7 + 11 + 13 + 17
        5 + 7 + 11 + 13 + 17

If only there was a simple way of performing the addition once, and then getting the individual sums of subsequences out of that pre-processed data in \$O(1)\$ time ...

Left to student.