### Project Euler Problem 27 Statement

Euler published the remarkable quadratic formula:

`n`² + `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² + 41 + 41 is clearly divisible by 41.

Considering quadratics of the form:

`n`² + `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.

### Solution

**Note:** *The quadratic formula needs only to generate prime numbers, not necessarily unique nor consecutive prime numbers.*

This problem is wanting us to find two coefficients, `a` and `b`, for a quadratic expression, `n ^{2} + an + b`,

`n`starting from zero and incremented by one until a non-prime is evaluated. The coefficients

`a`and

`b`are constrained as

`a`< 1000 and -1000 <

`b`< 1000.

Using a simple iteration of `a` and `b` over their range will produce a result for this specific problem, but takes too long for the more complex inquiry from HackerRank.

There are a few observations that will help improve performance.

`b` has to be prime

The problem requires our `n` to start at 0, and since we are looking for prime numbers with consecutive values of `n`, our first result from a quadratic expression would be 0^{2} – 0 + `b`, which evaluates simply to `b`. So `b` has to be positive, prime and less than 1000 (for this problem), which helps reduce the search space significantly.

Additionally, we can now start `n`

at 1 since we know the first outcome is guaranteed prime. Our sieve, `prime_sieve(L)`

, generates primes less than `L`

. Adding 1 to our limit, guarantees `L`

gets included should it be a prime number.

The prime number 2 is excluded from the possible starting primes as it evaluates to an even number after 1 or 2 iterations.

`1-a+b` must be odd and possibly prime

If you further consider when `n=1`, then the expression becomes `1-a+b` or `1+a+b`, which must always be evaluated to an odd number to yield a possible prime. We know `b` will always be an odd prime so `1+b` will be even. We can now infer that `a` must be odd and **| a| < b**.

HackerRank's Project Euler 27 adds the constraint that the coefficients `a` and `b` are in the range [-2000,-42] U [42,2000]. The positive constraint on `a` and `b` can be ignored, as we previously established, effectively halving the search range. We are asked to print the two coefficients `a` and `b` instead of the product of `a` and `b` as the original problem required.

#### HackerRank version

HackerRank simply changes the 1000 limit to any N, where 42 ≤ N ≤ 2000.

### Python Source Code

```
from Euler import prime_sieve, is_prime
L = int(input())
nmax = 0
for b in prime_sieve(L+1)[1:]: #start with prime number 3
for a in range(-b+2, 0, 2):
n = 1
while is_prime(n*n + a*n + b): n += 1
if n>nmax: nmax, p = n, (a,b)
print (p[0],p[1])
```

### Last Word

- Look at the repl.it for the
`prime_sieve`

and`is_prime`

functions.