Detailed mathematical approach

Problem Summary

Let \(p_1=2,p_2=3,p_3=5,\dots\) be the primes in increasing order. For each \(i\ge 1\), define \(A_i\) as the smallest positive integer satisfying

$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$

The problem asks for the sum \(S(n)\) of all primes \(q \le n\) that divide at least one of these values \(A_i\). The sequence grows extremely fast, so the solution cannot build large integers naively. Instead, it extends the Chinese Remainder system one prime at a time and tracks only residues.

Mathematical Approach

The entire method rests on viewing each \(A_i\) as one stage of an incremental Chinese Remainder Theorem construction.

Step 1: Define the CRT State

For each stage \(i\), let

$M_i=\prod_{k=1}^{i} p_k.$

Because the moduli \(p_1,p_2,\dots,p_i\) are pairwise coprime, the Chinese Remainder Theorem gives a unique residue class modulo \(M_i\) satisfying

$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$

We may choose the least positive representative as \(A_i\). The first stage is immediate:

$A_1=1,\qquad M_1=2.$

So the problem becomes: as this CRT solution is extended from \(i\) to \(i+1\), which later primes ever divide the current representative?

Step 2: Only Later Primes Can Contribute

Suppose \(q=p_j\) is the \(j\)-th prime. Once \(q\) has entered the system, every later term satisfies

$A_i \equiv j \pmod{q}\qquad(i \ge j).$

But \(j \lt p_j=q\), so this residue is never \(0\) modulo \(q\). Therefore \(q\) can divide some \(A_i\) only before its own congruence has been imposed, that is, only for stages \(i \lt j\).

This observation is crucial: at stage \(i\), it is enough to test only the primes \(p_{i+1},p_{i+2},\dots\). Any prime already built into the CRT system can no longer be a divisor.

Step 3: Derive the One-Step CRT Extension

Assume \(A_i\) is known modulo \(M_i\). Every number preserving the first \(i\) congruences has the form

$A_i + M_i t,$

for some integer \(t\). To create \(A_{i+1}\), we impose the new condition

$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$

Substituting \(A_{i+1}=A_i+M_i t\) gives

$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$

Since \(p_{i+1}\) is a new prime, it is coprime to \(M_i\), so \(M_i\) has a modular inverse modulo \(p_{i+1}\). Hence

$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$

This determines the next CRT state uniquely modulo \(M_{i+1}=M_i p_{i+1}\).

Step 4: Track Everything by Residues

The values \(A_i\) become enormous, but divisibility by a prime \(q\) depends only on the residue \(A_i \bmod q\). So for every prime \(q \le n\), the implementation stores two running residues:

$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$

After computing the correction \(t\) from the previous step, these residues update by

$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$

$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$

Now the hit test is exact and cheap:

$q \mid A_i \iff a_i(q)=0.$

Each prime is marked at most once, so the final answer is simply the sum of all marked primes.

Step 5: Worked Example for \(n=50\)

The checkpoint in the implementations is \(S(50)=69\). The first stages show why.

Start with

$A_1=1.$

No later prime divides \(1\).

For the next prime \(3\), solve

$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$

so \(t \equiv 2 \pmod{3}\) and therefore

$A_2=5.$

This already gives a hit, because \(5\mid A_2\).

Next, extend to prime \(5\):

$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$

Since \(6 \equiv 1 \pmod{5}\), we get \(t \equiv 3\), so

$A_3=23.$

Thus \(23\mid A_3\), giving the second contributing prime.

For the next step,

$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$

which yields

$A_4=53.$

This does not contribute to \(S(50)\) because \(53 \gt 50\). Continuing the same residue updates eventually reaches

$A_{10}=5765999453,$

and this value is divisible by \(41\). No other prime up to \(50\) ever hits, so

$S(50)=5+23+41=69.$

How the Code Works

The C++, Python, and Java implementations first generate all primes up to the requested limit with a standard sieve. They then initialize the CRT state at the first prime, corresponding to \(A_1=1\) and \(M_1=2\).

From that point on, the implementation never needs the full huge integer \(A_i\). Instead, it keeps one array containing the current residue of the CRT solution modulo each prime up to the limit, and a second array containing the current residue of the running modulus \(M_i\) modulo those same primes.

At each stage, the implementation scans only the primes that have not yet entered the CRT system. If the stored residue is \(0\), that prime divides the current \(A_i\) and is marked for inclusion in the final sum. Then the code computes the unique correction factor \(t\) modulo the next prime using a modular inverse obtained from the extended Euclidean algorithm, and updates both residue arrays in parallel. After all stages, it adds the marked primes.

Complexity Analysis

Let \(m=\pi(n)\), the number of primes up to \(n\). The sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. The main CRT process performs a triangular number of divisibility checks and residue updates, namely about

$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$

so the dominant cost is \(O(m^2)\) time. The stored prime list, the two residue arrays, and the hit markers together use \(O(m)\) additional memory.

Footnotes and References

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