Detailed mathematical approach

Problem Summary

We seek the sum of all integers \(n < 150{,}000{,}000\) for which the six values $n^2+1,\ n^2+3,\ n^2+7,\ n^2+9,\ n^2+13,\ n^2+27$ are prime, while the odd values between them, $n^2+5,\ n^2+11,\ n^2+15,\ n^2+17,\ n^2+19,\ n^2+21,\ n^2+23,\ n^2+25,$ are composite. Because the primes must be consecutive inside that window, those eight exclusions are part of the definition of a valid \(n\), not an optional afterthought.

A brute-force search would examine far too many large numbers near \(2.25\times 10^{16}\). The successful strategy is to force \(n\) into a tiny set of residue classes, precompute modular obstructions for many small primes, and reserve exact primality testing for the few candidates that survive all cheap filters.

Mathematical Approach

Let $G=\{1,3,7,9,13,27\},\qquad C=\{5,11,15,17,19,21,23,25\}.$ Then \(n\) is a solution exactly when \(n^2+g\) is prime for every \(g\in G\) and \(n^2+c\) is composite for every \(c\in C\).

The required and forbidden offsets

If \(n\) is even, then \(n^2\) is even, so every even offset produces an even number greater than 2 and is automatically composite. That is why only the odd offsets matter. The implementation therefore tracks two explicit sets: the six offsets that must produce primes and the eight odd offsets in the same interval that must not.

Congruence restrictions from small primes

Several modular arguments remove almost all integers before any primality test is attempted.

If \(n\) were odd, then \(n^2+1\) would be even and larger than 2, so \(n\) must be even.

Modulo 5, the quadratic residues are \(0,1,4\). If \(n^2\equiv 1\pmod 5\), then \(n^2+9\equiv 0\pmod 5\). If \(n^2\equiv 4\pmod 5\), then \(n^2+1\equiv 0\pmod 5\). Therefore the only surviving case is \(n^2\equiv 0\pmod 5\), which forces \(5\mid n\).

Modulo 3, a multiple of 3 would make \(n^2+3\), \(n^2+9\), and \(n^2+27\) divisible by 3, so \(3\nmid n\).

The strongest restriction comes from modulo 7. The quadratic residues mod 7 are \(0,1,2,4\). If \(n^2\equiv 0\pmod 7\), then \(n^2+7\) is divisible by 7. If \(n^2\equiv 1\pmod 7\), then \(n^2+13\equiv 0\pmod 7\). If \(n^2\equiv 4\pmod 7\), then \(n^2+3\equiv 0\pmod 7\). Only \(n^2\equiv 2\pmod 7\) survives, which is equivalent to \(n\equiv \pm 3\pmod 7\).

Combining \(2\mid n\), \(5\mid n\), and \(n\equiv \pm 3\pmod 7\) leaves exactly two arithmetic progressions: $n\equiv 10 \pmod{70}\qquad\text{or}\qquad n\equiv 60 \pmod{70}.$ The same mod-7 argument automatically makes \(n^2+5\) and \(n^2+19\) divisible by 7, so two forbidden offsets are eliminated for free.

Worked example: \(n=10\)

The smallest candidate already exhibits the full pattern. For \(n=10\), we have \(n^2=100\), so the required values are $101,\ 103,\ 107,\ 109,\ 113,\ 127,$ and each of them is prime. The forbidden odd offsets give $105,\ 111,\ 115,\ 117,\ 119,\ 121,\ 123,\ 125,$ and each of those is composite. So \(10\) is a genuine solution and a concrete illustration of the exact condition being tested.

A residue sieve for many small primes

The fixed mod-70 reduction is only the first layer. For each small prime \(p\) up to 2000, the implementations precompute the bad residue set $R_p=\{r\in\{0,\dots,p-1\}: r^2+g\equiv 0\pmod p\text{ for some }g\in G\}.$ If \(n\bmod p\in R_p\), then at least one required value is divisible by \(p\), so the candidate can be discarded immediately.

Primes 2 and 5 are omitted from this table because divisibility by them has already been absorbed into the forced form \(n\equiv 0\pmod{10}\). For very small \(n\), a congruence \(n^2+g\equiv 0\pmod p\) could still mean \(n^2+g=p\), which is prime rather than composite. The implementations avoid that edge case by activating these precomputed tables only once \(n\ge 1000\), a conservative threshold well above \(\sqrt{2000}\).

Exact verification after filtering

After the modular screens, the surviving candidates are rare. Each survivor is then checked exactly: the six values \(n^2+g\) must be prime and the eight values \(n^2+c\) must be composite. Since $n^2+27 < (150{,}000{,}000)^2+27 < 2.25\times 10^{16},$ every tested integer fits comfortably in 64-bit arithmetic, so fast Miller-Rabin based certification is practical for the last stage.

How the Code Works

Scanning only the two valid progressions

The C++, Python, and Java implementations iterate only over the sequences \(70m+10\) and \(70m+60\). This is the direct payoff of the congruence analysis: instead of checking all integers, the search immediately keeps only about one out of every 35 candidates.

Maintaining squares and modular states incrementally

Inside one progression, the step size is always 70, so the square is updated by the recurrence $ (n+70)^2=n^2+140n+4900.$ That avoids recomputing \(n^2\) from scratch. The same incremental idea is used for every small-prime filter: if the current residue modulo \(p\) is known, the next one is obtained by adding \(70\bmod p\). The sieve phase therefore becomes a sequence of cheap table lookups instead of repeated modular squaring.

The decision pipeline and parallel search

Each candidate passes through a short pipeline: inexpensive divisibility checks for 3 and 13, lookup in the precomputed bad-residue tables, exact primality tests on the six required offsets, and exact compositeness checks on the eight forbidden offsets. When every condition succeeds, the candidate \(n\) is added to the running sum.

The interval splits naturally into independent chunks. The C++ and Java implementations parallelize those chunks directly, and the Python implementation can also distribute chunks across worker processes. The mathematics is identical in all three languages; only the execution strategy changes.

Complexity Analysis

Let \(L\) be the search limit and \(B\) the upper bound for the small-prime residue tables. Building the tables costs \(O(B\log\log B+\sum_{p\le B} p)\) time and \(O(\sum_{p\le B} p)\) memory, because each prime \(p\) stores a boolean array of length \(p\).

The main scan visits only about \(L/35\) integers because it uses two residue classes modulo 70. For each candidate it performs constant-time arithmetic plus one residue update per sieve prime, and only a tiny fraction survive to the primality stage. With the fixed choice \(B=2000\) used by the implementations, memory usage stays small and the running time is effectively linear in the search limit.

Footnotes and References

1. Problem page: Project Euler 146
2. Prime constellations: Wikipedia - Prime k-tuple
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Quadratic residues: Wikipedia - Quadratic residue
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test
6. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes