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 and in , 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, itself has to be prime, because we test . Next we test , so we need , that is . 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.

### Like this:

Like Loading...

*Related*

Tags: nah, prime, prob27, quadratic

This entry was posted on September 27, 2009 at 9:48 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply