🔒 Problem

Considering quadratics of the form:

$n^2 + an + b$, where $ |a| < 1000 $ and $|b| ≤ 1000$ where $|n|$ is the modulus/absolute value of $n$

e.g. $|11| = 11$ and $|-4| = 4$

Find the product of the coefficients, $a$ and $b$, for the quadratic expression that produces the maximum number of primes for consecutive values of $n$, starting with $n = 0$.

🔐 Key Idea

using the property of prime numbers to optimize loops

🔑 Solution

🧭 Initial idea

$O(n^3)$ complexity.

Simplifying the formula $ n^2 + an + b $ into $ n (n + a) + b $, we can derive the following properties for the variables in the formula.

  1. Since $ n^2 + an + b $ must be prime, both $ n $ and $ b $, $ n + a $ and $ b $ must be prime.
  2. Since $ n^2 + an + b $ must be prime when $ n = 0 $, $ b $ must be prime.
  3. Since $ n $ is consecutive from 0, pair $ (0, b) $, $ (a, b) $, $ (1, b) $, $ (a + 1, b) $, ... must be prime accordingly.
  4. Since $ b $ must be prime and $ |b| ≤ 1000 $, possible values of $ b $ is prime numbers not exceeding 1000.

🧬 Properties applied in code

From property 1 and 3, the conditional statement if n % b is 0 or (n + a) % b is 0 was derived and added in order to optimize iteration.

From property 2, the iteration starts with n = 1 because b is always prime since it's from the precalculated list of primes.

From property 4, all primes not exceeding 1000 were calculated into b_list. Additionally, using for i in range(3, 1000 + 1, 2): ..., we excluded all even numbers from the iteration.

🧾 Pseudocode 

calculate all possible values of b

for all b:
    for n from 0:
        for a from -999 to 999:
            if n and n + a are prime to b:
                check whether n + 1 and n + 1 + a are prime, n + 2 and n + 2 + a are prime ... 
                repeat until n + k or n + k + a are not prime
def is_prime(n):
    for f in range(2, int(n ** 0.5)):
        if n % f is 0:
            return False
    return True

b_list = [2]

for i in range(3, 1000 + 1, 2):
    if is_prime(i):
        b_list.append(i)

max = 0
coef_a = 0
coef_b = 0

for b in b_list:
    for a in range(-999, 1000):
        count = 1
        n = 1

        while n * (n + a) + b > 1:
            if n % b is 0 or (n + a) % b is 0:
                break  # not prime with b

            if is_prime(n * (n + a) + b):
                count += 1
                n += 1
            else:
                break
        
        if count > max:
            max = count
            coef_a = a
            coef_b = b

print(coef_a * coef_b)

-59231

Note: Add if n < 2: return False in is_prime() function in order to make it complete.