// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 27 Solution

Project Euler 27 Solution

Project Euler 27: Find a quadratic formula that produces the maximum number of primes for consecutive values of n


Project Euler 27 Problem Description

Project Euler 27: 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, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² − 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² + 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.

Analysis

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, to a quadratic expression, n² + an + b, that 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 < a < 1000 and -1000 < b < 1000.

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

The 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 equation would be 02 – 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.

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 evaluate to an odd number to yield a possible prime. We know b+1 will be even so a must be odd. We can now infer that a must be odd and |a| < b which supports our thinking.

HackerRank Project Euler 27 adds the constraint that the coefficients a and b 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.

Project Euler 27
This program and method
solves all test cases for
Project Euler 27 on HackerRank

Project Euler 27 Solution

Runs < 0.070 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 27 Solution Python 2.7 source.

Afterthoughts

Project Euler 27 Solution last updated

Discussion

No comments yet.

Post a comment