Euler discovered the remarkable quadratic formula:
\[n^2 + n + 41\]It turns out that the formula will produce \(40\) primes for the consecutive integer values \(0 \le n \le 39\). However, when \(n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41\) is divisible by \(41\), and certainly when \(n = 41, 41^2 + 41 + 41\) is clearly divisible by \(41\).
The incredible formula \(n^2 - 79n + 1601\) was discovered, which produces \(80\) primes for the consecutive values \(0 \le n \le 79\). The product of the coefficients, \(-79\) and \(1601\), is \(-126479\).
Considering quadratics of the form:
\(n^2 + an + b\), where \(|a| \lt 1000\) and \(|b| \le 1000\)where \(|n|\) is the modulus/absolute value of \(n\)
e.g. \(|11| = 11\) and \(|-4| = 4\)
Find the product of the coefficients, \(a\) and \(b\), for the quadratic expression that produces the maximum number of primes for consecutive values of \(n\), starting with \(n = 0\).
I wish my code here did something clever, but the only optimizations it makes are rudimentary. First, \(b\) must be prime because of the case \(n = 0\). Second, \(a\) must be odd, otherwise \(n^2 + an + b\) would be even for all \(n \geq 1\).
It's worth noting that \(n^2 - 79n + 1601 = (n-40)^2 + (n-40) + 41\), so the second formula just gives the same primes as the first, only twice. The correct solution ends up being another such derivation, namely \((n-31)^2 + (n-31) + 41\). However, this fact is not easily explicable, so a full search is the most honest approach.
from sympy import primerange, isprime
def p27():
max_streak, res = 0, 0
for b in primerange(1000):
for a in range(-999, 1001, 2):
for n in range(b+1):
if not isprime(n**2 + a*n + b):
if n > max_streak:
max_streak, res = n, a * b
break
return res