Quadratic Primes

Question

I'm asking about Project Euler problem 27 (https://projecteuler.net/problem=27). I have written a piece of code that either doesn't work, or doesn't work fast enough - I'm new to programming and don't fully understand the meaning of the error I'm receiving.

Anyway, the question is asking me to find which integers $a,b$ with $|a|,|b|<1000$ lead to $n^2 + an + b$ producing the biggest collection of consecutive primes starting with $n=0$. First of all, we notice that $b$ must itself be prime in order for the $n=0$ term to be prime and start the chain. I therefore wrote a piece of code that loops b over all possible prime values and then checks each and every integer $-1000 < a < 1000$ and measures the length of the chain of consecutive primes produced. I've included it below:

n=int(input("Set a bound for range of a and b: "))


def is_prime(n):
if n==1:
    return False
elif n==2 or n==3:
    return True
elif (n % 2 == 0) or (n % 3 == 0):
    return False
elif all(n % i != 0 for i in range(2, ceil(n**0.5+1))):
    return True
else:
    return False

def seive(n):
primes=[]
for i in range(n):
    if is_prime(i)==True:
        primes.append(i)
for j in primes: #j can't be allowed to be negative since when m=0 (the first term), we must have m**2+k*m+j prime. Therefore j must be chosen from primes
    for k in range(-n,n,1):
        chain=[]
        for m in range(0,n):
            while is_prime(m**2+k*m+j) == True and m**2+k*m+j>0:
                chain.append(m**2 + k*m + j)
                details = [j,k,len(chain)]
return details

print(seive(n))

Could someone please either explain what I've done wrong and give me a hint on how to get it working? Thanks!

Answer 1

Analysing the problem yields a couple of constraints, like e.g. that b must be prime or that a must be greater than 1 - b. However, the possible range for a and b is so tiny that it is not worth it to find such constraints and to incorporate them into the solution - it only creates additional opportunities for making mistakes and shooting oneself in the foot.

The only constraint worthy of consideration is that n^2 + a*n + b must be divisible by n when n is a multiple of b. Hence the chain of primes must stop at n = b at the latest, which gives a ceiling for the maximum possible number that might have to be checked for primality. That is to say, the largest possible candidate for the primality test must be less than 2,000,000. This gives a useful limit when using set membership instead of trial division as a primality test.

As rossum hinted at in a comment, the task is not to find the last tested set of coefficients and the resulting chain length. You are asked to find the coefficients a and b that give the longest chain of primes, and to print the product of that pair. Hence you need to change the way you process the 'chain test' and its results.

Perhaps you'll understand your code better if you clean it up a bit and remove redundancies (e.g. is_prime(x) implies x >= 2 and hence x > 0; it just doesn't make sense to put a test for positiveness after a test for primality). It should also be helpful to refactor the code so that individual bits and pieces have only one single responsibility and can be tested/tuned separately before being integrated into the whole shebang.

Once you got your code into working shape you might want to post it over on Code Review, which is a much more appropriate venue for the kind of feedback you seem to be looking for.

P.S.: constraints like the ones I mentioned at the beginning become very interesting indeed when you try to push the envelope, but for solving the problem as stated it is best to go for the simplest-possible solution. It shouldn't take more than a few fractions of a second even in Python.