notes.html
problem 27 · 30 lines
<article>
<h3>Problem Analysis</h3>
<p>
This problem asks me to search a family of <a class="reference-source" href="https://en.wikipedia.org/wiki/Quadratic_function" rel="noopener noreferrer" target="_blank">quadratic</a> expressions of the form <code>n^2 + an + b</code>, with integer coefficients bounded by <code>|a| < 1000</code> and <code>|b| <= 1000</code>. For each pair <code>(a, b)</code> I feed in consecutive non-negative integers <code>n = 0, 1, 2, ...</code> and count the longest unbroken run of <a class="reference-source" href="https://en.wikipedia.org/wiki/Prime_number" rel="noopener noreferrer" target="_blank">prime numbers</a> the formula produces before the first non-prime value. The answer is the product <code>a * b</code> for the pair with the longest run.
</p>
<p>
The single observation that makes this tractable is a boundary condition. At <code>n = 0</code> the formula collapses to just <code>b</code>, so if <code>b</code> is not prime the run has length zero. Only prime values of <code>b</code> can ever begin a meaningful run. Since there are only 168 primes below 1000, this insight shrinks the candidate set for <code>b</code> from 2001 integers to roughly 168 magnitudes (each usable with either sign). The remaining work is a brute-force scan over the ~1000 values of <code>a</code>. Each primality test is done by <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> at <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(sqrt(V))</a> cost per value. With <code>P</code> primes, <code>A</code> values of <code>a</code>, runs of length at most <code>R</code> (~80), and values up to <code>V_max</code> (~2 * 10^6), the overall cost is roughly <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(P * A * R * sqrt(V_max))</a> - large in the abstract, but fast in practice because almost all runs collapse after a handful of steps.
</p>
<h3>Solution Approach</h3>
<h4>Sieve-constrained brute-force search</h4>
<p>
The Python and C files share index 0: they implement the same algorithm, with the C version being a direct translation that benefits from compiled arithmetic in the hot inner loop. I describe the algorithm once and note the language-specific differences as they arise.
</p>
<p>
<strong>Step 1 - Generate prime candidates for b.</strong> I generate all primes up to the limit (1000) using the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sieve of Sundaram</a>. This sieve operates entirely on odd numbers: it marks every integer of the form <code>i + j + 2ij</code> (for positive integers <code>i, j</code>) as composite within an array of size <code>(N-1)/2</code>; each surviving index <code>i</code> corresponds to the odd prime <code>2i + 1</code>, and the prime 2 is added explicitly. I chose <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Sundaram" rel="noopener noreferrer" target="_blank">Sundaram</a> over 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> mainly for variety; at this problem size both have equivalent cost, and the Sundaram array is half the size since it skips even numbers.
</p>
<p>
<strong>Step 2 - Restrict the parity of a.</strong> For every odd prime <code>b</code> the code steps <code>a</code> in increments of 2 starting from 1; only <code>b = 2</code> uses step 1 from 0. The reasoning is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Parity_(mathematics)" rel="noopener noreferrer" target="_blank">parity</a> argument. With odd <code>b</code>, consider <code>n = 1</code>: the value is <code>1 + a + b</code>. For this to be prime (and not 2, which would force a very short run for these magnitudes) it must be odd, so <code>a</code> must be odd. Exploring only odd magnitudes of <code>a</code> therefore covers all coefficient pairs that can produce a long run while halving the iteration count - a cheap arithmetic filter applied before the expensive primality tests.
</p>
<p>
<strong>Step 3 - Enumerate sign combinations.</strong> Rather than looping <code>a</code> from -999 to 999 and <code>b</code> over both signs, I loop <code>a</code> from 0 upward and <code>b</code> over positive primes only, then evaluate all four signed pairs explicitly: <code>(+a, +b)</code>, <code>(+a, -b)</code>, <code>(-a, -b)</code>, <code>(-a, +b)</code>. Their products are <code>+ab</code>, <code>-ab</code>, <code>+ab</code>, <code>-ab</code> respectively, computed inline so no extra multiplication is needed. These four cover every distinct signed combination for a given pair of magnitudes.
</p>
<p>
<strong>Step 4 - Measure the prime run.</strong> The helper <code>prime_run(a, b)</code> increments <code>x</code> from 0 and tests whether <code>|x^2 + ax + b|</code> is prime, stopping at the first failure and returning the count. I take the absolute value before the test because negative integers are never prime, and a negative output simply ends the run - taking the magnitude lets me detect both signs uniformly. In C the value is held in a <code>long long</code> to avoid <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_overflow" rel="noopener noreferrer" target="_blank">integer overflow</a>, since the quadratic can reach roughly 2 * 10^6.
</p>
<p>
<strong>Step 5 - Track the best result.</strong> In Python I build a list of <code>(run_length, product)</code> <a class="reference-source" href="https://en.wikipedia.org/wiki/Tuple" rel="noopener noreferrer" target="_blank">tuples</a> and call <code>max()</code>, which compares lexicographically: the longest run wins, and ties break on the larger product. The C version replicates this exactly with explicit comparisons (<code>run > best_run</code>, then <code>products[c] > best_product</code> on a tie).
</p>
</article>