Project Euler # 27 using Python

Question

This Project Euler question has me a little bewildered.

Here is my solution that I thought was correct:

import math
start = time.time()
def check_prime(a, b, n):
    num = n**2 + a * n + b
    mod = 3
    if num >= 0:
        check = int(math.sqrt(num))
    else:
        return False
    while mod <= check:
        if num % mod == 0:
            return False
        mod += 2
    return True
def main():
    n = 0
    max_n = 0
    for a in xrange(-1000, 1000):
        for b in xrange(-1000, 1000):
            while check_prime(a, b, n):
                n += 1
                if n > max_n:
                    max_n = n
                    product = a * b
        n = 0
    print max_n, product
    print time.time() - start
if __name__ == '__main__':
    main()

This gives me a consecutive prime list of 376 where the actual list is only 71. I think I am just having difficulty understanding the question. Wouldn't the longest prime list have to be at least 80 since that is the one given as an example? My program computes the product of the two terms for the 71 list, but then it keeps going up to 376.

Is there something in the question I am overlooking?

Answer 1

Below my answer in python. It runs in last than 5 seconds but there is surely more optimal solution to it. Yet in my answer the algorithm is pretty readable.

# ==== Problem 27 ====

def is_prime(n: int) -> bool:
    if n <= 1:
        return False
    for i in range(2, int(np.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def poly_loop(a: int, b:int) -> []:
    n = 1
    tmp = n**2 + a*n + b
    ls_sol=[]
    while is_prime(tmp) is True:
        ls_sol.append(tmp)
        n = n + 1
        tmp = n**2 + a*n + b

    return ls_sol

ls_tmp = []
length_ls = 0
ls_sol = [0, 0] # [a, b]

for a in range(0, 1000): # a
    for b in range(0, 1001): # b
        ls_tmp = poly_loop(a,b)
        if len(ls_tmp)>length_ls:
            length_ls = len(ls_tmp)
            ls_sol[0] = a
            ls_sol[1] = b
        ls_tmp = poly_loop(a, -b)
        if len(ls_tmp) > length_ls:
            length_ls = len(ls_tmp)
            ls_sol[0] = a
            ls_sol[1] = -b
        ls_tmp = poly_loop(-a, b)
        if len(ls_tmp) > length_ls:
            length_ls = len(ls_tmp)
            ls_sol[0] = -a
            ls_sol[1] = b
        ls_tmp = poly_loop(-a, -b)
        if len(ls_tmp) > length_ls:
            length_ls = len(ls_tmp)
            ls_sol[0] = -a
            ls_sol[1] = -b

print(f"Solution are a= {ls_sol[0]}, b= {ls_sol[1]}")

Answer 2

Wouldn't the longest prime list have to be at least 80 since that is the one given as an example?

The formula given in the problem statement is n² 79n + 1601, so a = 79 and b = 1601 > 1000. Therefore, you shouldn't expect the number of consecutive primes to be greater than 80. In fact, 71 is the correct number of consecutive primes. Now you just need to make sure your product is correct.

Hint:

the value of a * b is negative.