Detailed mathematical approach

Problem Summary

Let \(P(m)\) denote the largest prime factor of \(m\). For nine consecutive integers define

$S(n)=\sum_{j=0}^{8} P(n+j).$

The task is to determine the maximum value of \(S(n)\) for starting points up to \(10^{16}\). A direct scan is hopeless: the search range is enormous, and each trial value of \(n\) would require factoring nine nearby integers. The implementations therefore do something more structured: they force several offsets to contain prescribed small factors, then check whether the remaining quotients are prime.

Mathematical Approach

The central idea is to build arithmetic progressions in which the numbers \(n,n+1,\dots,n+8\) already have a favorable factorization pattern. If the large quotients are prime, then those quotients are automatically the largest prime factors we want to sum.

Step 1: Force a Useful Divisibility Pattern

The search works modulo

$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$

First impose

$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$

Then \(n+4\) is divisible by \(9\), \(5\), and \(7\), so

$315 \mid (n+4).$

Next choose one of the two residues

$n\equiv 1 \pmod{16}\qquad \text{or}\qquad n\equiv 7 \pmod{16}.$

If \(n\equiv 1 \pmod{16}\), then the odd offsets satisfy

$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$

If \(n\equiv 7 \pmod{16}\), the powers of two are redistributed as

$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$

Because \(n\equiv 5 \pmod 9\), both \(n+1\) and \(n+7\) are also divisible by \(3\). So the odd offsets always receive the divisor multiset

$\{6,4,2,24\},$

although the exact placement of these four divisors depends on which of the two residues modulo \(16\) is chosen.

Step 2: Exclude More Small Prime Divisors with CRT

The construction also requires

$n\equiv 1\text{ or }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ or }4 \pmod{13}.$

These choices ensure that none of the nine numbers \(n,n+1,\dots,n+8\) is divisible by \(11\) or \(13\): the corresponding residue intervals never hit \(0\) modulo those primes. Combining all independent choices gives

$2\cdot 2\cdot 4=16$

admissible residue classes modulo \(M\). The Chinese Remainder Theorem turns the congruences above into 16 explicit residues \(r\), and every candidate examined by the program satisfies

$n\equiv r \pmod M$

for one of those residues.

Step 3: Convert Largest Prime Factors into Quotients

For one representative residue family the nine numbers take the form

$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$

The mirrored family simply permutes the four odd-offset divisors from \((6,4,2,24)\) to \((24,2,4,6)\). In either case the small divisor \(d_j\) contains only primes from \(\{2,3,5,7\}\). If the quotient \(q_j\) is prime, then \(q_j\) is automatically larger than every prime dividing \(d_j\), so

$P(n+j)=q_j=\frac{n+j}{d_j}.$

Therefore, on a fully successful candidate, the target sum becomes a linear expression in \(n\). For the displayed family,

$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$

The mirrored family has the same coefficient of \(n\), because it uses the same reciprocal multiset

$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$

This matters because the score increases as \(n\) increases, so once a residue class is fixed we only care about the nearest admissible candidates below the top of the range.

Step 4: Reparameterize the Search by a Single Index

Let

$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$

For each admissible residue \(r\), the implementations examine candidates of the form

$n=N_0+r-Mk,\qquad 0\le k<10^7.$

This converts the original search over \(n\) into a one-dimensional scan over \(k\). Since every step decreases \(n\) by exactly \(M\), and the score is affine in \(n\) once the divisor pattern is fixed, smaller \(k\) means a better candidate inside the same residue class.

Step 5: Mark Forbidden Indices with a Prime Sieve

The sieve uses every prime \(p\) with

$17\le p<10^8.$

These are exactly the primes not already handled by the residue construction. Because \(p\nmid M\), the inverse \(M^{-1}\pmod p\) exists. For any offset \(j\), the condition that the quotient at that offset be divisible by \(p\) is equivalent to

$N_0+r+j-Mk\equiv 0 \pmod p,$

so the bad values of \(k\) lie in the arithmetic progression

$k\equiv (N_0+r+j)M^{-1}\pmod p.$

Thus each prime marks at most one residue class of \(k\) for each of the nine offsets. Unmarked indices are precisely the candidates for which none of the nine reduced quotients has a prime divisor between \(17\) and \(10^8-1\).

Step 6: Why Sieving up to \(10^8\) Is Enough

The largest reduced quotient is on the order of \(10^{16}\), so its square root is about \(10^8\). The smallest reduced quotient comes from dividing by \(315\), and

$\sqrt{\frac{10^{16}}{315}}<10^8.$

Hence every quotient checked by the program has square root below the sieve limit. If a positive quotient survives all prime divisors up to \(10^8\), it has no divisor up to its square root and must be prime. That turns the modular sieve into a full primality certificate for the reduced numbers.

Worked Example: The Embedded Checkpoint at \(n=100\)

The implementations contain a small verification example before the full search. Direct factorization gives

$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$

Therefore

$S(100)=5+101+17+103+13+7+53+107+3=409.$

The same checkpoint scan also verifies that

$\max_{2\le n\le 100} S(n)=417.$

This example is small enough to check directly, and it confirms that the largest-prime-factor definition is being interpreted correctly before the residue-class sieve is run on the real bound.

How the Code Works

The C++, Python, and Java implementations all use the same mathematical plan. First they build the 16 admissible residues produced by the CRT constraints. Next they generate all primes from \(17\) up to \(10^8-1\), and for each such prime they precompute the modular inverse of \(M\).

Each worker then processes one subset of the residue classes. For one residue class it allocates a byte array of length \(10^7\), one slot for each index \(k\). For every prime and every offset \(j=0,\dots,8\), it marks the arithmetic progression of indices that would make the corresponding reduced quotient divisible by that prime. After the marking phase, the unmarked indices are the surviving candidates.

Finally the implementation evaluates the quotient-based score for each surviving candidate and keeps the maximum over all residue classes. The Python entry point delegates to the same native search logic, while the Java version implements the same sieve-and-scan strategy directly.

Complexity Analysis

Let \(B=10^8\) and \(K=10^7\). Building the prime table up to \(B\) costs \(O(B\log\log B)\) time and \(O(B)\) memory. For one residue class, the marking work is

$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$

followed by one linear scan of \(K\) flags. Since there are only 16 residue classes, the overall asymptotic cost is still \(O(B\log\log B+K\log\log B)\) up to a fixed constant factor. In practice the dominant memory cost is the prime sieve plus one \(K\)-sized marker array per worker thread.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=526
2. Prime factor: Wikipedia — Prime factor
3. Chinese Remainder Theorem: Wikipedia — Chinese remainder theorem
4. Modular multiplicative inverse: Wikipedia — Modular multiplicative inverse
5. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes