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+1601was 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 nn 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



In [11]:

    
def prime_factors(n): # from eratosthenes
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
            
    return factors

def is_prime(n):
    return len(prime_factors(n)) == 1

assert is_prime(n=2) == True
assert is_prime(n=4) == False

max_params = { 'a': 0, 'b': 0, 'num_prime': 0 }

def f(a,b,n):
    return n**2 + a*n + b

for a in range(-1000+1, 1000):
    for b in range(-1000, 1001):
        n = 0
        while is_prime(f(a,b,n)):
            n += 1
        if n-1 > max_params['num_prime']:
            max_params = { 'a': a, 'b': b, 'num_prime': n-1 }
            print max_params
print max_params['a']*max_params['b']









    



{'a': -996, 'num_prime': 1, 'b': 997}
{'a': -499, 'num_prime': 2, 'b': 997}
{'a': -325, 'num_prime': 3, 'b': 977}
{'a': -245, 'num_prime': 4, 'b': 977}
{'a': -197, 'num_prime': 5, 'b': 983}
{'a': -163, 'num_prime': 6, 'b': 983}
{'a': -131, 'num_prime': 7, 'b': 941}
{'a': -121, 'num_prime': 8, 'b': 947}
{'a': -105, 'num_prime': 10, 'b': 967}
{'a': -61, 'num_prime': 70, 'b': 971}
-59231



In [ ]: