Project Euler Problem 27 Solution: Quadratic primes

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² + 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$ which will generate the most prime numbers when evaluated with $n$ starting from zero and incremented by one until a non-prime is evaluated. The coefficients $a$ and $b$ are constrained as $-1000\lt a\lt 1000$ and $-1000\lt b\lt 1000$.

While a straightforward iteration over the ranges of $a$ and $b$ can yield a solution for this particular problem, it becomes inefficient for addressing the more complex challenges posed by HackerRank.

Here are a few observations that will help improve performance.

$b$ has to be prime

The problem requires $n$ to start at $0$. Since we are searching for prime numbers generated by consecutive values of $n$, the first result from the quadratic expression $0^2+0+b$ simplifies to $b$. Thus, $b$ must be a positive prime number less than $1000$ (as specified in this problem), which significantly reduces the search space.

Since $n=0$ is a prime number, we can begin our search from $n=1$. $2$ is excluded from the set of possible starting primes because, after 1 or 2 iterations, it always results in an even, non-prime number.

$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| \lt b$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 27

HackerRank Project Euler 27 changes the limit to 42 ≤ N ≤ 2000. We are asked to print the two coefficients a and b instead of the product of a and b.

Python Source Code

import Euler

m = 0
s = [i for i in range(3, int(input())+1, 2) if Euler.is_prime(i)]
for b in s:
    for a in range(-b+2,0,2):
        n = 1
        while Euler.is_prime(n*n+a*n+b): n+= 1
        if n>m: m,r = n,(a,b)

print(*r)

Last Word

The is_prime function will be imported instead of hard coded into the source code. This provides flexibility to include different functions as required to solve a problem.