Detailed mathematical approach

Problem Summary

We study the quadratic family \(q_{a,b}(n)=n^2+an+b\) under the bounds \(|a| \lt 1000\) and \(|b| \le 1000\). For each choice of coefficients, we start at \(n=0\) and ask how long the values stay prime without interruption. The task is to find the pair \((a,b)\) with the longest initial prime streak and return the product \(ab\).

Inside these bounds, the best pair is \(a=-61\) and \(b=971\). It produces 71 consecutive primes for \(n=0,1,\dots,70\), so the required product is \(-59231\).

Mathematical Approach

Let \(\mathbb{P}\) denote the set of positive primes, and let \(L(a,b)\) be the length of the initial prime run generated by \(q_{a,b}(n)\):

$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$

If the values at \(n=0,1,\dots,k-1\) are all prime, then \(L(a,b)=k\). The problem is therefore a finite maximization problem over all allowed coefficient pairs.

The first value fixes \(b\)

At \(n=0\), the polynomial is simply

$q_{a,b}(0)=b.$

So \(b\) itself must be prime. Because the primality test used by the implementations rejects every integer below 2, this means \(b\) must in fact be a positive prime. Mathematically, that already removes the overwhelming majority of the nominal \(|b|\le 1000\) search interval.

The second value constrains the parity of \(a\)

The next term is

$q_{a,b}(1)=1+a+b.$

If \(b\) is an odd prime, then \(1+b\) is even, so \(q_{a,b}(1)\) has the same parity as \(a\). To remain prime and exceed 2, this value should usually be odd, which strongly suggests that successful choices of \(a\) are odd once \(b>2\). The implementations do not exploit this observation, but it explains part of the structure of the winning search region.

The value at \(n=b\) gives a structural bound

Substituting \(n=b\) reveals a useful factorization:

$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$

Since \(b\) is prime, this term is automatically divisible by \(b\). Therefore a prime run will normally break no later than \(n=b\), because \(q_{a,b}(b)\) is then forced to be composite. The only way around that divisibility trap is the exceptional case

$b+a+1=1 \quad\Longrightarrow\quad a=-b,$

which makes \(q_{a,b}(b)=b\) prime again. This identity is not used as a pruning rule in the code, but it is a genuine problem-specific invariant and shows why long runs are rare.

Why a direct search is enough

The coefficient box is small, and most pairs fail quickly. For each admissible pair, one evaluates

$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$

until the first non-prime value appears. All three implementations use the same simple primality test: reject \(n<2\), handle the even case separately, then try odd divisors up to \(\sqrt{n}\). No sieve, recurrence, or deeper number theory is required for this problem size.

Worked example: the winning quadratic

The maximizing polynomial is

$q(n)=n^2-61n+971.$

Its first values are

$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$

and the prime streak continues all the way to \(n=70\). The last prime in that initial block is

$q(70)=70^2-61\cdot 70+971=1601,$

while the next value is

$q(71)=71^2-61\cdot 71+971=1681=41^2.$

So this pair produces exactly 71 consecutive primes, and no admissible pair produces more.

How the Code Works

Enumerating coefficient pairs

The C++, Python, and Java implementations scan every integer \(a\) from \(-999\) to \(999\) and every integer \(b\) from \(-999\) to \(999\). This is effectively the Project Euler search box, because the only omitted endpoints are \(\pm 1000\), and neither is prime. Before any streak is counted, the implementation checks whether \(b\) itself is prime and skips the pair immediately if it is not.

Counting a prime streak

For each surviving pair, the implementation starts with \(n=0\), computes \(n^2+an+b\), and stops as soon as the result fails the prime test. Negative values, 0, and 1 therefore end the loop at once. The number of successful iterations is exactly the mathematical quantity \(L(a,b)\).

Keeping the best pair and validating the search

Whenever a newly tested pair yields a longer streak than the current record, the stored best coefficients are updated. Before the full search, the implementations also support self-checks using the classical examples \(n^2+n+41\) and \(n^2-79n+1601\), verifying streak lengths 40 and 80. The second example lies outside the final coefficient bounds, but it is still a useful correctness test for the counting routine.

Complexity Analysis

Let \(A=999\) and \(B=999\). The raw scan touches \((2A+1)(2B+1)=1999^2\) coefficient pairs, but only those with prime \(b\) require a full streak count. Since there are 168 positive primes at most 999, the more expensive part is closer to

$1999\times 168 \approx 3.36\times 10^5$

candidate quadratics.

If a given pair survives for \(K\) terms and the largest tested value has size about \(M\), then trial division costs \(O(K\sqrt{M})\) for that pair. In this problem \(K\) never exceeds 71 inside the search box, so the runtime is easily manageable. Memory usage is \(O(1)\): the implementations keep only loop counters, the current polynomial value, and the best pair found so far.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=27
2. Prime number: Wikipedia - Prime number
3. Trial division: Wikipedia - Trial division
4. Quadratic polynomial: Wikipedia - Quadratic polynomial
5. Prime-generating formulas: Wikipedia - Formula for primes