Problem #27 is one of the many problems on Project Euler that concerns prime numbers. Here is the question:
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 ≤ n ≤ 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≤n≤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| ≤ 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.
With 1999 possible values of a and 2001 possible values of b, it would be quite difficult to check all possible pairs (a,b). Luckily, we don’t have to:
Solution #1: Sieve Approach
We can observe that if f(n) = n^2 + an + b, then f(0) = b and f(1) = 1 + a + b. Because we know the maximum chain of primes has at least 2 elements, we know that both b and (1+a+b) must be prime. b must be a prime between 2 and 1000 inclusive by the contents of the problem. Based on the value of b, a must be chosen such that (1+a+b) is a prime between 2 and 2000 inclusive. Given these facts, we can check every possible pair (a,b) that satisfies these specific conditions to greatly reduce the potential number of pairs.
To do this, we create a sieve of the primes from 2 to 1000 for the potential values of b and then a sieve of the primes from 2 to 2000 for the potential values of a. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #27
'''
import time
from math import sqrt
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return myPrimes
def isPrime(n):
if(n>1 and n<4):
return True
if(n%2==0 or n<=1):
return False
c = 3
while(c<=sqrt(n)):
if(n%c==0):
return False
c+=2
return True
def projectEulerProblemTwentySeven(n):
bPossible = sieveEratosthenes(n)
aPossible = sieveEratosthenes(2*n)
maximumSequence = 40
maxA = 1
maxB = 41
for x in bPossible:
for y in aPossible:
if abs(y-x-1)>=n:
break
b = x
a = y-x-1
i = 2
while(True):
if(isPrime(i*i+a*i+b):
i+=1
else:
break
if(i>maximumSequence):
maximumSequence = i
maxA = a
maxB = b
return maxA*maxB
start = time.time()
print projectEulerProblemTwentySeven(1000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
-59231
--- 0.0769238471985 seconds ---
for input of n = 1000
'''
Once again, prime sieves appear to be very helpful in solving Project Euler questions.
That’s all for today, folks. Thanks for reading!
The Inner Machinations of Walker 