Quadratic Primes

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| < 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$.

This is a classic problem that can be solved using a combination of prime number theory and an efficient programming approach.

1. Extend Euler’s idea of a prime-generating quadratic of the form $n^2 + an + b$.
2. Start with the observation that if $n = 0$, then the quadratic expression equals $b$, which must be prime. As all primes except $2$ are odd, $b$ should be an odd prime (since we are looking for maximum number of primes, $b = 2$ yields fewer primes).
3. Also note that if $n = 1$, then the quadratic expression equals $1 + a + b$. As this expression must also be prime and all primes except $2$ are odd, $1 + a + b$ should be odd, i.e., $a$ should be even. However, $a$ also needs to be less than $1000$ and greater than $-1000$, hence $a$ should be an even number in the range $[-1000, 1000]$.
4. $b$, on the other hand, should be a prime number less than or equal to $1000$.

With these conditions, we can program a computer to loop through all the possibilities for $a$ and $b$. For each possibility of $a$ and $b$, check how many consecutive primes are produced for increasing values of $n$, starting from $n = 0$. Then, pick the pair $(a, b)$ that produces the most primes. The product $ab$ is then the answer.

In Python, for instance, you can implement the Sieve of Eratosthenes to generate all primes up to $1000$, and then check every combination of these primes and the possible values of $a$. For each combination, calculate the number of primes produced and remember the maximum number found.

You’ll find that the $a$ and $b$ pair that give the largest number of consecutive primes are $a = -61$ and $b = 971$ which gives a product $ab = -59231$ as the answer. This quadratic produces primes for $n$ in $0 \le n \le 70$. If you are interested in the Python code to solve this problem, I can provide it in the next response.

More Answers: