Project Euler, Problem 27: 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 \leq n \leq 39

. However, when

n = 40

40^{2} + 40 + 41 = 40 (40 + 1) + 41

is divisble by 41, and certainly when

n = 41

41^{2} + 41 + 41

is clearly divisble by 41.

The incredible formula

n^{2} - 79 n + 1601

was discovered, which produces 80 primes for the consecutive values

0 \leq n \leq 79

. The product of the coefficients, -79 and 1601, is -126479.

Considering quadratics of the form:

n^{2} + a n + b

, where

| a | < 1000

and

| b | \leq 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

To begin with, I saw that the term $b$ had to be prime and positive because $n^{2} + a n + b$ where $n = 0$ is just $b$ . I used a sieve of Eratosthenes to generate primes up to 1,000 to try.

For $a$ , my only insight was that it had to be odd because $n^{2} + a n$ is always even for odd numbers but always odd for $n = 1$ . Because two odd numbers always sum to an even number, this meant $a$ could not be even.

Someone online helped me further refine my value for $a$ by pointing out that $1 + a + b$ also had to be prime and would shrink my list of possible values to check.

From here I 𝖈𝖗𝖚𝖓𝖈𝖍𝖊𝖉^®. I'm sure there's a better way, but this is how I got here. I don't know why $a$ is negative or why it's greater than -99.

85,511