Project Euler

Investigating a Prime Pattern

The smallest positive integer n for which the numbers n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, and n^2+27 are consecutive primes is 10. Find the sum of all integers n, 0 < n < 150,000,000, such that n^2...

Source sync Apr 19, 2026

Problem #0146

Level Level 06

Solved By 5,953

Languages C++, Python

Answer 676333270

Length 372 words

modular_arithmeticnumber_theoryalgebra

The smallest positive integer $n$ for which the numbers $n^2 + 1$, $n^2 + 3$, $n^2 + 7$, $n^2 + 9$, $n^2 + 13$, and $n^2 + 27$ are consecutive primes is $10$. The sum of all such integers $n$ below one-million is $1242490$.

What is the sum of all such integers $n$ below $150$ million?

Problem 146: Investigating a Prime Pattern

Mathematical Foundation

Theorem 1 (Parity constraint). For $n^2 + 1$ to be an odd prime (greater than 2), $n$ must be even.

Proof. If $n$ is odd, $n^2$ is odd, so $n^2 + 1$ is even. Since $n^2 + 1 > 2$ for $n > 1$ , it would be composite. For $n = 1$ : $n^2 + 1 = 2$ is prime but $n^2 + 3 = 4$ is not. Hence $n$ must be even. $\square$

Theorem 2 (Mod 3 constraint). We must have $n \not\equiv 0 \pmod{3}$ .

Proof. If $3 \mid n$ , then $n^2 \equiv 0 \pmod{3}$ , so $n^2 + 3 \equiv 0 \pmod{3}$ . Since $n^2 + 3 > 3$ for $n > 0$ , it would be composite. $\square$

Theorem 3 (Mod 5 constraint). We must have $n \equiv 0 \pmod{5}$ .

Proof. The quadratic residues mod 5 are $\{0, 1, 4\}$ . We check each:

$n^2 \equiv 0 \pmod{5}$ : offsets give $\{1,3,2,4,3,2\} \pmod{5}$ — none zero.
$n^2 \equiv 1 \pmod{5}$ : offsets give $\{2,4,3,0,4,3\} \pmod{5}$ — $n^2 + 9 \equiv 0$ , composite.
$n^2 \equiv 4 \pmod{5}$ : offsets give $\{0,2,1,3,2,1\} \pmod{5}$ — $n^2 + 1 \equiv 0$ , composite.

Only $n \equiv 0 \pmod{5}$ is viable. $\square$

Lemma 1 (Combined congruence). From Theorems 1—3: $n \equiv 0 \pmod{2}$ , $n \not\equiv 0 \pmod{3}$ , $n \equiv 0 \pmod{5}$ . Thus $n \equiv 10$ or $20 \pmod{30}$ .

Proof. By the Chinese Remainder Theorem, $n \equiv 0 \pmod{10}$ (from $2 \mid n$ and $5 \mid n$ ). Combined with $n \not\equiv 0 \pmod{3}$ : $n \bmod 30 \in \{10, 20\}$ . $\square$

Theorem 4 (Mod 7 refinement). Further modular analysis with $p = 7$ restricts $n \bmod 7$ to specific residues.

Proof. Quadratic residues mod 7 are $\{0, 1, 2, 4\}$ . For each residue $r = n^2 \bmod 7$ , check whether any offset $k \in \{1,3,7,9,13,27\}$ satisfies $r + k \equiv 0 \pmod{7}$ :

$r = 0$ : $0 + 7 \equiv 0$ — $n^2 + 7$ divisible by 7. Invalid (unless $n^2 + 7 = 7$ , impossible for $n > 0$ ).
$r = 1$ : offsets mod 7 are $\{2,4,1,3,0,0\}$ — $n^2+13 \equiv 0$ and $n^2+27 \equiv 0$ . Invalid.
$r = 2$ : offsets mod 7 are $\{3,5,2,4,1,1\}$ — none zero. Valid.
$r = 4$ : offsets mod 7 are $\{5,0,4,6,3,3\}$ — $n^2+3 \equiv 0$ . Invalid.

So $n^2 \equiv 2 \pmod{7}$ , i.e., $n \equiv 3$ or $4 \pmod{7}$ . $\square$

Theorem 5 (Consecutive primes condition). The “consecutive primes” requirement means that for all $k \in \{5, 11, 15, 17, 19, 21, 23, 25\}$ , $n^2 + k$ must be composite.

Proof. “Consecutive primes” means no prime exists strictly between $n^2+1$ and $n^2+27$ other than the six listed values. The integers between 1 and 27 not in $\{1,3,7,9,13,27\}$ are $\{2,4,5,6,8,10,11,12,14,15,16,17,18,19,20,21,22,23,24,25,26\}$ . Even offsets produce even $n^2 + k$ (since $n$ is even), which are automatically composite (greater than 2). The odd offsets to check are $\{5, 11, 15, 17, 19, 21, 23, 25\}$ . $\square$

Lemma 2 (Miller—Rabin sufficiency). Deterministic Miller—Rabin with witnesses $\{2, 3, 5, 7, 11, 13\}$ correctly determines primality for all integers up to $3.317 \times 10^{24}$ , which exceeds our maximum value of $n^2 + 27 < 2.25 \times 10^{16}$ .

Proof. This follows from the result of Jaeschke (1993) and subsequent computational verification: the witnesses $\{2, 3, 5, 7, 11, 13\}$ form a sufficient set for numbers below $3.317 \times 10^{24}$ . $\square$

Editorial

We precompute valid residues mod 210 = lcm(2, 3, 5, 7). We then quick composite checks for must-not-be-prime offsets. Finally, check consecutive: no primes at intermediate offsets.

Pseudocode

INPUT: Bound B = 150,000,000
OUTPUT: Sum of all valid n
Precompute valid residues mod 210 = lcm(2, 3, 5, 7)
Quick composite checks for must-not-be-prime offsets
Check consecutive: no primes at intermediate offsets
if ok

Complexity Analysis

Time: The modular sieve reduces candidates to $O(B / 210 \times |\text{valid residues}|) \approx O(B / 50)$ . Each candidate requires $O(14)$ Miller—Rabin tests, each costing $O(\log^2(n^2)) = O(\log^2 n)$ with modular exponentiation. Total: $O(B \log^2 B / 50)$ .
Space: $O(1)$ beyond the list of valid residues (which has $O(1)$ elements).

Answer

\boxed{676333270}

C++ project_euler/problem_146/solution.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

ll mod_mul(ll a, ll b, ll m) {
    return (lll)a * b % m;
}

ll mod_pow(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mod_mul(result, base, mod);
        base = mod_mul(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool miller_rabin(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ll x = mod_pow(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = mod_mul(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
        if (!miller_rabin(n, a)) return false;
    }
    return true;
}

int main() {
    // Precompute valid residues mod 210
    vector<int> valid;
    for (int r = 0; r < 210; r++) {
        if (r % 2 != 0) continue;
        if (r % 3 == 0) continue;
        if (r % 5 != 0) continue;
        // Check mod 7
        ll r2 = (ll)r * r;
        bool ok = true;
        for (int k : {1, 3, 7, 9, 13, 27}) {
            if ((r2 + k) % 7 == 0) { ok = false; break; }
        }
        if (ok) valid.push_back(r);
    }

    ll total = 0;
    int must_prime[] = {1, 3, 7, 9, 13, 27};
    int must_not_prime[] = {5, 11, 15, 17, 19, 21, 23, 25};

    for (int base = 0; base < 150000000; base += 210) {
        for (int r : valid) {
            ll n = base + r;
            if (n <= 0 || n >= 150000000) continue;
            ll n2 = n * n;

            bool ok = true;
            for (int k : must_prime) {
                if (!is_prime(n2 + k)) { ok = false; break; }
            }
            if (!ok) continue;

            for (int k : must_not_prime) {
                if (is_prime(n2 + k)) { ok = false; break; }
            }
            if (!ok) continue;

            total += n;
        }
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_146/solution.py

"""
Problem 146: Investigating a Prime Pattern

Find the sum of all n, 0 < n < 150,000,000, such that
n^2+1, n^2+3, n^2+7, n^2+9, n^2+13, n^2+27 are consecutive primes.
"""

def is_prime_miller_rabin(n):
    """Deterministic Miller-Rabin for n < 3.317e14 (sufficient witnesses)."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # For n < 3.317 * 10^14, witnesses {2,3,5,7,11,13,17} suffice.
    # Our max is ~(1.5e8)^2 + 27 ~ 2.25e16, so use more witnesses.
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, x, n) if False else (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True

def solve():
    LIMIT = 150_000_000

    # Precompute valid residues mod 210
    valid_residues = []
    for r in range(210):
        if r % 2 != 0:
            continue
        if r % 3 == 0:
            continue
        if r % 5 != 0:
            continue
        # Check mod 7
        r2 = r * r
        ok = True
        for k in [1, 3, 7, 9, 13, 27]:
            if (r2 + k) % 7 == 0:
                ok = False
                break
        if ok:
            valid_residues.append(r)

    must_be_prime = [1, 3, 7, 9, 13, 27]
    must_not_be_prime = [5, 11, 15, 17, 19, 21, 23, 25]

    total = 0
    for base in range(0, LIMIT, 210):
        for r in valid_residues:
            n = base + r
            if n <= 0 or n >= LIMIT:
                continue

            n2 = n * n

            ok = True
            for k in must_be_prime:
                if not is_prime_miller_rabin(n2 + k):
                    ok = False
                    break
            if not ok:
                continue

            for k in must_not_be_prime:
                if is_prime_miller_rabin(n2 + k):
                    ok = False
                    break
            if not ok:
                continue

            total += n

    print(total)

if __name__ == "__main__":
    solve()