Problem 27 – Prime Generating Quadratics

by

With my freshly minted PrimeOracle, I’m ready to attack problem 27, in which we are asked to find polynomials that generate long strings of consecutive primes starting when you plug in 0.

Basically my idea for this problem was to iterate through all of the choices for the coefficients a and b in n^2+an+b, and then for each polynomial plug in values until we hit a composite. Record maximums as appropriate.

There are a few easy optimizations to make. First, b itself has to be prime, because we test n=0. Next we test n=1, so we need 1+a+b\geq 2, that is a\geq 1-b. Those are the only optimizations I made, though I’m sure there are some more advanced ones out there.

So here’s my code:

# assume PrimeOracle.py is in the same directory as this file
from PrimeOracle import PrimeOracle

def solve(n):
    # seed our oracle to 2*n+2, since n=1 gives 1+a+b
    isprime = PrimeOracle(2*n + 2)
    maxp, maxn = 41, 40
    for b in [m for m in xrange(2, n) if isprime[m] ]:
        for a in xrange(1-b, n):
            idx = 1 # we already tesetd 0 with isprime[b]
            while(isprime[idx*idx+idx*a+b]):
                idx += 1
            if(idx - 1 > maxn):
                maxp, maxn = a*b, idx - 1
    return maxp

I had my oracle also tell me what the biggest number it was asked about was, and the answer was up around 12000. So we could change the starting seed in the oracle to be big enough to never have to extend, and probably save some time.

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: