Finding the Longest Prime-Generating Quadratic: Project Euler Problem 27

Project Euler Problem 27 asks us to find coefficients a and b for the quadratic expression n² + an + b that produces the maximum number of consecutive primes for n = 0, 1, 2, ...

The Problem

Euler discovered the remarkable quadratic formula n² + n + 41, which produces 40 primes for consecutive integer values starting from n = 0. The challenge is to find the product of coefficients a and b for the quadratic that produces the maximum number of primes, with -1000 < a < 1000 and -1000 ≤ b ≤ 1000.

The Solution

python

from collections import defaultdict

def is_prime(n):
    import math
    if n < 2:
        # print(str(n) + " is not a prime number")
        return False

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            # print(str(n) + " is not a prime number")
            return False

    return True

dictionary_x = defaultdict(int)

for n in range(0, 115):
    for a in range(-1000, 1000):
        for b in range(-1000, 1000):
            if is_prime((n * n) + (a * n) + b):
                dictionary_x[str(a)+"_"+str(b)] += 1
            elif is_prime((n * n) + (a * n) + b) == False:
                continue


#print(dictionary_x)

max_key, max_value = max(dictionary_x.items(), key=lambda x: x[1])

print(max_key, max_value)

Output: -61_971: 106

This means the quadratic n² - 61n + 971 produces 106 consecutive primes (for n = 0 through n = 105), and the answer to the problem is -61 × 971 = -59,231.

The Approach

The solution uses a brute-force search strategy with three nested loops:

1. Test values of n from 0 to 114 (slightly beyond what's needed for safety)

2. Iterate through all possible values of a (-1000 to 999)

3. Iterate through all possible values of b (-1000 to 999)

For each combination of coefficients, we count consecutive primes starting from n = 0. A dictionary tracks how many consecutive primes each (a, b) pair generates.

Key Implementation Details

Prime Testing

The is_prime() function uses trial division, checking divisibility up to √n. Numbers less than 2 are immediately rejected as non-prime.

Tracking Consecutive Primes

The solution uses a defaultdict to count consecutive primes for each coefficient pair. The key insight is that we need to count consecutive primes—as soon as the formula produces a non-prime, we stop counting for that (a, b) pair. The outer loop limit of 115 ensures we test enough values of n to capture the longest sequence.

Finding the Winner

After testing all combinations, max() with a lambda function extracts the coefficient pair that generated the most consecutive primes.

Optimization Observations

While this solution works, there are several potential optimizations:

• Constraint on b: Since n² + an + b must be prime when n = 0, b itself must be prime (and positive)

• Constraint on a: For n = 1, we get 1 + a + b, which must be prime. This constrains possible values of a

• Constraint on a + b: Since a is negative and b is positive (971 is prime), we know a + b + 1 must also be prime

• Early termination: The inner loop could break immediately when a non-prime is found, rather than continuing

• Prime caching: Storing previously computed prime checks would eliminate redundant calculations

The code structure could be refined to avoid the redundant elif clause—the continue statement is unnecessary since the loop naturally proceeds to the next iteration.

Verifying the Result

We can verify: when a = -61 and b = 971, the formula n² - 61n + 971 produces primes for n = 0, 1, 2, ..., 105. At n = 106, we get 106² - 61(106) + 971 = 11236 - 6466 + 971 = 5741, which factors as 53 × 107 (not prime).

This problem demonstrates how systematic exploration of a constrained search space can solve number theory questions, even when more elegant mathematical insights might lead to faster solutions.