Project Euler

Problem

This problem comes from Project Euler 27

Problem

Euler discovered the remarkable quadratic formula:

$n^2 + n + 41$

It turns out that the formula will produce 40 primes for the consecutive integer values $0 \leq n \leq 39$ . However, when $n=40$ , $40^2 + 40 + 41 = 40(40+1)+41$ is divisible by 41, and certainly when $n=41$ , $41^2 + 41 + 41$ is clearly divisible by 41.

The incredible formula $n^2 - 79n + 1601$ was discovered, which produces 80 primes for the consecutive values $0 \leq n \leq 79$ . . The product of the coefficients, -79 and 1601, is -126 479.

Considering quadratics of the form:

$n^2 + an + b$ ,
where $|a| \lt 1000$ and $|b| \leq 1000$
where $|n|$ is the modulus/absolute value of $n$
e.g $|11| = 1$ 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$

Solution

The problem gives two example equations:

Where $a=1$ and $b=41$ , and

Where $a=79$ and $b=1601$

We should first notice that $a$ and $b$ for both equations are prime numbers. We should try creating these equations using prime numbers for $a$ and $b$ .

To solve the problem, I came up with the following steps:

1. Create a list of positive primes and their negative counterparts
2. For a, loop through the list containing the negative and positive primes
3. For b, loop through the list containing the positive primes
4. For n, try all numbers up to 1000 until n doesn’t produce a prime
5. Save the longest prime chain

Why does #3 use only positive primes? Actually, it doesn’t have to, but from observing the output, only the positive prime numbers produce chains, so we can do away with trying the negative side.

Code

# Project Euler: Problem 27
# Quadratic Primes

from PEF import soe

max_a = 0
max_b = 0
max_count = 0

p_primes = soe(1000)
n_primes = [-p for p in p_primes]
primes = n_primes + p_primes

for a in primes:
    for b in p_primes:
        prime_count = 0
        for n in range(1001):
            if n*(n+a)+b in p_primes:
                prime_count += 1
                if prime_count > max_count:
                    max_a = a
                    max_b = b
                    max_count = prime_count
            else:
                break

print(max_a*max_b)