Euler discovered the remarkable quadratic formula:
$$n^2 + n + 41$$It turns out that the formula will produce 40 primes for the consecutive values $n$ = 0 to 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 $n$ = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.
Considering quadratics of the form:
$n^2 + an + b$, where $|a| < 1000$ and $|b| < 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$.
In [1]:
N = 1000000
prime = [False, False] + [True]*(N-2)
for k in range(2, N):
if prime[k]:
for m in range(k*k, N, k):
prime[m] = False
(max_n, max_a, max_b) = (0, 0, 0)
for b in range(1,1000):
if not prime[b]:
continue
for a in range(-999, 1000):
n = 1
while n*n+a*n+b > 0 and prime[n*n+a*n+b]:
n += 1
if n > max_n:
max_n, max_a, max_b = n, a, b
print(max_a*max_b)
In [ ]: