Problem 27: Quadratic Primes

Project Euler Problem 27 Solution

EulerSolve provides an optimized solution for Project Euler Problem 27, Quadratic Primes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We study the quadratic family $q_{a,b}(n)=n^2+an+b$ under the bounds $|a| \lt 1000$ and $|b| \le 1000$. For each choice of coefficients, we start at $n=0$ and ask how long the values stay prime without interruption. The task is to find the pair $(a,b)$ with the longest initial prime streak and return the product $ab$. Inside these bounds, the best pair is $a=-61$ and $b=971$. It produces 71 consecutive primes for $n=0,1,\dots,70$, so the required product is $-59231$. Mathematical Approach Let $\mathbb{P}$ denote the set of positive primes, and let $L(a,b)$ be the length of the initial prime run generated by $q_{a,b}(n)$: $$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$ If the values at $n=0,1,\dots,k-1$ are all prime, then $L(a,b)=k$. The problem is therefore a finite maximization problem over all allowed coefficient pairs. The first value fixes $b$ At $n=0$, the polynomial is simply $$q_{a,b}(0)=b.$$ So $b$ itself must be prime. Because the primality test used by the implementations rejects every integer below 2, this means $b$ must in fact be a positive prime. Mathematically, that already removes the overwhelming majority of the nominal $|b|\le 1000$ search interval....

Detailed mathematical approach

Problem Summary

We study the quadratic family $q_{a,b}(n)=n^2+an+b$ under the bounds $|a| \lt 1000$ and $|b| \le 1000$. For each choice of coefficients, we start at $n=0$ and ask how long the values stay prime without interruption. The task is to find the pair $(a,b)$ with the longest initial prime streak and return the product $ab$.

Inside these bounds, the best pair is $a=-61$ and $b=971$. It produces 71 consecutive primes for $n=0,1,\dots,70$, so the required product is $-59231$.

Mathematical Approach

Let $\mathbb{P}$ denote the set of positive primes, and let $L(a,b)$ be the length of the initial prime run generated by $q_{a,b}(n)$:

$$L(a,b)=\min\{n\ge 0 : q_{a,b}(n)\notin \mathbb{P}\}.$$

If the values at $n=0,1,\dots,k-1$ are all prime, then $L(a,b)=k$. The problem is therefore a finite maximization problem over all allowed coefficient pairs.

The first value fixes $b$

At $n=0$, the polynomial is simply

$$q_{a,b}(0)=b.$$

So $b$ itself must be prime. Because the primality test used by the implementations rejects every integer below 2, this means $b$ must in fact be a positive prime. Mathematically, that already removes the overwhelming majority of the nominal $|b|\le 1000$ search interval.

The second value constrains the parity of $a$

The next term is

$$q_{a,b}(1)=1+a+b.$$

If $b$ is an odd prime, then $1+b$ is even, so $q_{a,b}(1)$ has the same parity as $a$. To remain prime and exceed 2, this value should usually be odd, which strongly suggests that successful choices of $a$ are odd once $b>2$. The implementations do not exploit this observation, but it explains part of the structure of the winning search region.

The value at $n=b$ gives a structural bound

Substituting $n=b$ reveals a useful factorization:

$$q_{a,b}(b)=b^2+ab+b=b(b+a+1).$$

Since $b$ is prime, this term is automatically divisible by $b$. Therefore a prime run will normally break no later than $n=b$, because $q_{a,b}(b)$ is then forced to be composite. The only way around that divisibility trap is the exceptional case

$$b+a+1=1 \quad\Longrightarrow\quad a=-b,$$

which makes $q_{a,b}(b)=b$ prime again. This identity is not used as a pruning rule in the code, but it is a genuine problem-specific invariant and shows why long runs are rare.

Why a direct search is enough

The coefficient box is small, and most pairs fail quickly. For each admissible pair, one evaluates

$$q_{a,b}(0),\ q_{a,b}(1),\ q_{a,b}(2),\ \dots$$

until the first non-prime value appears. All three implementations use the same simple primality test: reject $n<2$, handle the even case separately, then try odd divisors up to $\sqrt{n}$. No sieve, recurrence, or deeper number theory is required for this problem size.

Worked example: the winning quadratic

The maximizing polynomial is

$$q(n)=n^2-61n+971.$$

Its first values are

$$q(0)=971,\qquad q(1)=911,\qquad q(2)=853,$$

and the prime streak continues all the way to $n=70$. The last prime in that initial block is

$$q(70)=70^2-61\cdot 70+971=1601,$$

while the next value is

$$q(71)=71^2-61\cdot 71+971=1681=41^2.$$

So this pair produces exactly 71 consecutive primes, and no admissible pair produces more.

How the Code Works

Enumerating coefficient pairs

The C++, Python, and Java implementations scan every integer $a$ from $-999$ to $999$ and every integer $b$ from $-999$ to $999$. This is effectively the Project Euler search box, because the only omitted endpoints are $\pm 1000$, and neither is prime. Before any streak is counted, the implementation checks whether $b$ itself is prime and skips the pair immediately if it is not.

Counting a prime streak

For each surviving pair, the implementation starts with $n=0$, computes $n^2+an+b$, and stops as soon as the result fails the prime test. Negative values, 0, and 1 therefore end the loop at once. The number of successful iterations is exactly the mathematical quantity $L(a,b)$.

Keeping the best pair and validating the search

Whenever a newly tested pair yields a longer streak than the current record, the stored best coefficients are updated. Before the full search, the implementations also support self-checks using the classical examples $n^2+n+41$ and $n^2-79n+1601$, verifying streak lengths 40 and 80. The second example lies outside the final coefficient bounds, but it is still a useful correctness test for the counting routine.

Complexity Analysis

Let $A=999$ and $B=999$. The raw scan touches $(2A+1)(2B+1)=1999^2$ coefficient pairs, but only those with prime $b$ require a full streak count. Since there are 168 positive primes at most 999, the more expensive part is closer to

$$1999\times 168 \approx 3.36\times 10^5$$

candidate quadratics.

If a given pair survives for $K$ terms and the largest tested value has size about $M$, then trial division costs $O(K\sqrt{M})$ for that pair. In this problem $K$ never exceeds 71 inside the search box, so the runtime is easily manageable. Memory usage is $O(1)$: the implementations keep only loop counters, the current polynomial value, and the best pair found so far.

Footnotes and References

Problem page: https://projecteuler.net/problem=27
Prime number: Wikipedia - Prime number
Trial division: Wikipedia - Trial division
Quadratic polynomial: Wikipedia - Quadratic polynomial
Prime-generating formulas: Wikipedia - Formula for primes

Problem 27 source code

C++

#include <cstdint>
#include <iostream>
#include <string>

namespace {

using i64 = std::int64_t;

struct Options {
    int abs_a = 999;
    int abs_b = 999;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--abs-a=", options.abs_a)) {
            continue;
        }
        if (parse_int_after_prefix(arg, "--abs-b=", options.abs_b)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.abs_a >= 0 && options.abs_b >= 0;
}

bool is_prime(const i64 n) {
    if (n < 2) {
        return false;
    }
    if ((n & 1LL) == 0LL) {
        return n == 2;
    }
    for (i64 p = 3; p <= n / p; p += 2) {
        if (n % p == 0LL) {
            return false;
        }
    }
    return true;
}

int consecutive_prime_count(const int a, const int b) {
    int n = 0;
    while (true) {
        const i64 value = static_cast<i64>(n) * static_cast<i64>(n) +
                          static_cast<i64>(a) * static_cast<i64>(n) +
                          static_cast<i64>(b);
        if (!is_prime(value)) {
            break;
        }
        ++n;
    }
    return n;
}

int solve(const int abs_a, const int abs_b) {
    int best_a = 0;
    int best_b = 0;
    int best_count = -1;

    for (int a = -abs_a; a <= abs_a; ++a) {
        for (int b = -abs_b; b <= abs_b; ++b) {
            if (!is_prime(b)) {
                continue;
            }
            const int count = consecutive_prime_count(a, b);
            if (count > best_count) {
                best_count = count;
                best_a = a;
                best_b = b;
            }
        }
    }

    return best_a * best_b;
}

bool run_checkpoints() {
    if (consecutive_prime_count(1, 41) != 40) {
        std::cerr << "Checkpoint failed for n^2+n+41" << '\n';
        return false;
    }
    if (consecutive_prime_count(-79, 1601) != 80) {
        std::cerr << "Checkpoint failed for n^2-79n+1601" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.abs_a, options.abs_b) << '\n';
    return 0;
}

Python

import sys

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    p = 3
    while p * p <= n:
        if n % p == 0:
            return False
        p += 2
    return True

def consecutive_prime_count(a, b):
    n = 0
    while True:
        value = n * n + a * n + b
        if not is_prime(value):
            break
        n += 1
    return n

def solve(abs_a, abs_b):
    best_a = 0
    best_b = 0
    best_count = -1

    for a in range(-abs_a, abs_a + 1):
        for b in range(-abs_b, abs_b + 1):
            if not is_prime(b):
                continue
            count = consecutive_prime_count(a, b)
            if count > best_count:
                best_count = count
                best_a = a
                best_b = b

    return best_a * best_b

def run_checkpoints():
    if consecutive_prime_count(1, 41) != 40:
        sys.stderr.write("Checkpoint failed for n^2+n+41\n")
        return False
    if consecutive_prime_count(-79, 1601) != 80:
        sys.stderr.write("Checkpoint failed for n^2-79n+1601\n")
        return False
    return True

def parse_int_after_prefix(arg, prefix):
    if not arg.startswith(prefix):
        return False, None
    tail = arg[len(prefix):]
    if not tail:
        return False, None
    try:
        value = int(tail)
        if value < 0:
            return False, None
        return True, value
    except ValueError:
        return False, None

def main():
    abs_a = 999
    abs_b = 999
    run_checkpoints_flag = True
    
    args = sys.argv[1:]
    for arg in args:
        if arg == "--skip-checkpoints":
            run_checkpoints_flag = False
        else:
            success, value = parse_int_after_prefix(arg, "--abs-a=")
            if success:
                abs_a = value
                continue
            success, value = parse_int_after_prefix(arg, "--abs-b=")
            if success:
                abs_b = value
                continue
            sys.stderr.write(f"Unknown argument: {arg}\n")
            return 1
    
    if abs_a < 0 or abs_b < 0:
        sys.stderr.write("Invalid arguments\n")
        return 1
    
    if run_checkpoints_flag and not run_checkpoints():
        return 2
    
    print(solve(abs_a, abs_b))

if __name__ == "__main__":
    main()

Java

class Euler27 {

    private static class Options {
        int abs_a = 999;
        int abs_b = 999;
        boolean run_checkpoints = true;
    }

    private static boolean parse_int_after_prefix(String arg, String prefix, java.util.function.IntConsumer setter) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }

        int parsed = 0;
        for (int i = 0; i < tail.length(); i++) {
            char c = tail.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }
            parsed = parsed * 10 + (c - '0');
        }
        setter.accept(parsed);
        return true;
    }

    private static boolean parse_arguments(String[] args, Options options) {
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                options.run_checkpoints = false;
                continue;
            }
            if (parse_int_after_prefix(arg, "--abs-a=", val -> options.abs_a = val)) {
                continue;
            }
            if (parse_int_after_prefix(arg, "--abs-b=", val -> options.abs_b = val)) {
                continue;
            }

            System.err.println("Unknown argument: " + arg);
            return false;
        }

        return options.abs_a >= 0 && options.abs_b >= 0;
    }

    private static boolean is_prime(long n) {
        if (n < 2) {
            return false;
        }
        if ((n & 1L) == 0L) {
            return n == 2;
        }
        for (long p = 3; p <= n / p; p += 2) {
            if (n % p == 0) {
                return false;
            }
        }
        return true;
    }

    private static int consecutive_prime_count(int a, int b) {
        int n = 0;
        while (true) {
            long value = (long)n * n + (long)a * n + b;
            if (!is_prime(value)) {
                break;
            }
            ++n;
        }
        return n;
    }

    private static int solve(int abs_a, int abs_b) {
        int best_a = 0;
        int best_b = 0;
        int best_count = -1;

        for (int a = -abs_a; a <= abs_a; ++a) {
            for (int b = -abs_b; b <= abs_b; ++b) {
                if (!is_prime(b)) {
                    continue;
                }
                int count = consecutive_prime_count(a, b);
                if (count > best_count) {
                    best_count = count;
                    best_a = a;
                    best_b = b;
                }
            }
        }

        return best_a * best_b;
    }

    private static boolean run_checkpoints() {
        if (consecutive_prime_count(1, 41) != 40) {
            System.err.println("Checkpoint failed for n^2+n+41");
            return false;
        }
        if (consecutive_prime_count(-79, 1601) != 80) {
            System.err.println("Checkpoint failed for n^2-79n+1601");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parse_arguments(args, options)) {
            System.exit(1);
        }

        if (options.run_checkpoints && !run_checkpoints()) {
            System.exit(2);
        }

        System.out.println(solve(options.abs_a, options.abs_b));
    }
}