Consecutive Prime Sum¶

Another way to phrase this problem is that we're looking for the longest subsequence of primes $p_i, p_{i+1}, p_{i+2}, \ldots, p_{j-1}$ that sum to a prime below 1000000.

If we let $p_0 = 2$, then $p_{41537} = 499979$, $p_{41538} = 500009$, and $p_{41539} = 500029$. Since $p_{41538} + p_{41539} > 1000000$, there's no point in checking any sum that's composed with a prime greater than 500010.

In [1]:
primes = prime_range(500010)

Now here's an algorithm for finding the longest consecutive prime sum. The clever bit about this algorithm is that it avoids repeatedly recalculating large sums - instead, we slide through the list of primes, growing and shrinking a running total. (As much as I'd like to take credit for this algorithm, the steps were outlined by the user tzaman on the problem thread.)

In [2]:
def longest_consecutive_prime_sum(primes):
    total = 0
    end = 0
    best = (0, 0)
    for begin in range(0, len(primes)):
        # grow the sum until it's larger than 1000000
        for maximum in range(end, len(primes)):
            total += primes[maximum]
            if total >= 1000000:
                break

        # shrink the sum until it's prime (or shorter than our best sum so far)
        for end in reversed(range(begin, maximum + 1)):
            total -= primes[end]
            
            if end - begin <= best[1] - best[0]:
                break

            if is_prime(total):
                best = (begin, end)
                break

        # try again, starting one prime after our current start point
        total -= primes[begin]
    
    return best

The algorithm returns the indices of the slice that's the longest sum.

In [3]:
i, j = longest_consecutive_prime_sum(primes)
i, j
Out[3]:
(3, 546)

The longest prime sum starts at $p_3$ and ends with $p_{545}$.

In [4]:
sum(primes[i:j])
Out[4]:
997651

Relevant sequences¶

  • Primes expressible as the sum of (at least two) consecutive primes in at least 1 way: A067377

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.