notes.html

problem 50 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
I am asked to find the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime</a> below one million that can be written as the sum of the most <em>consecutive</em> primes. The naive reading of this problem invites an O(n^3) catastrophe: for every starting prime, try every length, and for every candidate length re-add a run of primes and test the total for primality. The two ideas that collapse this into something fast are a <a class="reference-source" href="https://en.wikipedia.org/wiki/Prefix_sum" rel="noopener noreferrer" target="_blank">prefix sum</a> array and monotonicity-based pruning. A prefix sum array <code>S</code> stores running totals, so that <code>S[k]</code> is the sum of the first <code>k</code> primes; the sum of any contiguous block from index <code>j</code> to <code>i-1</code> is then just <code>S[i] - S[j]</code>, computed in constant time. Without it, every candidate sum is a fresh O(n) scan.
</p>
<p>
Two observations prune the search. First, because all primes are positive, the prefix sums are strictly increasing - so as I shrink <code>j</code>, the candidate sum <code>S[i] - S[j]</code> grows monotonically, and once it crosses the limit, every longer run from the same endpoint also crosses it and I can stop immediately. Second, I only care about runs <em>longer</em> than the best found so far, so I start the inner loop at <code>j = i - best_length - 1</code> and never even look at runs that cannot improve the answer. Primality of each candidate is settled in O(1) by a Boolean sieve - an array indexed by value where the entry is true exactly when that value is prime. Building the sieve costs O(n log log n); the doubly-nested loop, thanks to the two prunes, runs in near-linear time in practice. The dominant cost is therefore the sieve itself.
</p>
<h3>Solution Approach</h3>
<h4>Prefix-Sum Sieve Search (Python and C)</h4>
<p>
Both <code>p0050_s0.py</code> and <code>p0050_s0.c</code> implement the same four-step algorithm; they differ only in idiom and arithmetic width.
</p>
<p>
<strong>Step 1 - Generate primes.</strong> I generate all primes up to <code>max_limit</code> with the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>. Sundaram works on odd numbers only: it marks every value of the form <code>i + j + 2*i*j</code> as composite, then maps each surviving index <code>i</code> to the odd prime <code>2*i + 1</code>, prepending the prime 2. I chose it largely for variety - the more familiar <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a> is in the same complexity class and would serve equally well. The output is a dense ascending array of primes.
</p>
<p>
<strong>Step 2 - Build the prefix-sum array.</strong> I build <code>prime_sums</code> with <code>prime_sums[0] = 0</code> and <code>prime_sums[k]</code> equal to the sum of the first <code>k</code> primes. That leading zero is a sentinel: it lets a run starting at the very first prime be written as <code>prime_sums[i] - prime_sums[0]</code>, in exactly the same form as every other run, so the inner loop needs no special case.
</p>
<p>
<strong>Step 3 - Build a fast primality lookup.</strong> In Python I make a <code>set</code> from the prime tuple, giving O(1) average membership tests. In C I <code>calloc</code> a byte array of size <code>max_limit + 1</code> and set <code>is_prime[p] = 1</code> for each prime - O(1) worst-case lookup with excellent cache behaviour.
</p>
<p>
<strong>Step 4 - Double-loop search with pruning.</strong> The outer loop advances the right endpoint index <code>i</code>. The inner loop starts at <code>j = i - best_length - 1</code> rather than <code>i - 1</code>, so any larger <code>j</code> - which would yield a run no longer than the current best - is skipped outright. As <code>j</code> decrements, the candidate <code>prime_sums[i] - prime_sums[j]</code> grows; the moment it exceeds <code>max_limit</code> I <code>break</code>. When a candidate is prime, I record the new best length and best value. The C version additionally guards <code>j_start &lt; 0</code> with a <code>continue</code> and checks <code>possible_prime &gt;= 2</code> before indexing the sieve.
</p>
<p>
<strong>Language differences.</strong> Python uses <a class="reference-source" href="https://docs.python.org/3/library/itertools.html#itertools.accumulate" rel="noopener noreferrer" target="_blank">itertools.accumulate</a> to build the prefix sums in one compiled call, and relies on arbitrary-precision integers so overflow is impossible. The C version builds the prefix sums in a manual loop and stores them as <code>long long</code> (64-bit), because the sum of all primes below one million is roughly 37 billion - far past the 32-bit signed limit of about 2.1 billion. That difference in arithmetic, plus Python's dynamic dispatch, explains why the C version is roughly 60 times faster on the main case (0.0026 s versus 0.1615 s).
</p>
</article>