Detailed mathematical approach

Problem Summary

For each positive integer \(n\), define \(p(n)\) to be the first prime \(p\) for which

$ (n \bmod p)\bmod 7 \ne 0. $

Equivalently, every earlier prime \(q<p(n)\) must satisfy \(n \bmod q \in \{0,7,14,\dots\}\), and \(p(n)\) is the first prime where that pattern breaks. The quantity to compute is

$ A(N)=\sum_{n=1}^{N} p(n), $

with the actual input \(N=10^{17}\). A direct search over all \(n\) is impossible. The successful idea is to group integers by congruence classes and move those classes from prime to prime.

Mathematical Approach

The solution processes primes in increasing order and keeps track of the integers that have survived every test so far.

The survivor invariant

Let \(p_1=2,p_2=3,\dots\) be the primes. After all primes up to \(p_k\) have been checked, define

$ S_k=\{n\le N : n \bmod q \in \{0,7,14,\dots\}\text{ for every prime } q\le p_k\}. $

These are exactly the numbers whose first failing prime is still larger than \(p_k\). If we write \(C_k=|S_k|\), then the numbers that disappear when the next prime \(p\) is processed contribute

$ p\,(C_k-C_{k+1}) $

to the final sum, because all of them satisfy \(p(n)=p\). So the entire problem becomes: update the survivor set efficiently and count it after each prime.

Residue classes modulo the accumulated prime product

After processing a prime prefix, set

$ M_k=\prod_{q\le p_k} q. $

Whether \(n\) belongs to \(S_k\) depends only on its remainders modulo the processed primes, so it depends only on \(n \pmod{M_k}\). That means \(S_k\) can be represented by a finite list of surviving residue classes \(r \pmod{M_k}\).

For a new prime \(p\), the allowed remainders are the multiples of \(7\) below \(p\):

$ \mathcal{A}_p=\{0,7,14,\dots\}\cap[0,p-1]. $

There are only \(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\) such residues. For small primes \(p<7\), the only allowed remainder is \(0\), so the early stages simply enforce divisibility by \(2\), then \(3\), then \(5\), then \(7\).

Lifting one surviving class with the Chinese remainder theorem

Suppose \(r \pmod{M_k}\) is a surviving class, and let \(a\in\mathcal{A}_p\) be an allowed residue modulo the next prime \(p\). We need the integers satisfying

$ x\equiv r \pmod{M_k},\qquad x\equiv a \pmod p. $

Write \(x=r+M_k t\). Then \(t\) must solve

$ M_k t \equiv a-r \pmod p. $

Because \(p\) is a new prime, \(\gcd(M_k,p)=1\), so \(M_k\) has an inverse modulo \(p\). Hence

$ t\equiv (a-r)\,M_k^{-1}\pmod p, $

and every pair \((r,a)\) produces one unique child residue modulo \(M_kp\):

$ x\equiv r+M_k t \pmod{M_kp}. $

This is the crucial compression step. Instead of testing every integer one by one, the algorithm lifts only the residue classes that are still alive.

Counting how many integers a residue class contributes

Once a class \(r \pmod M\) is known to survive, its members in \([1,N]\) are easy to count. If \(r>0\), the class contributes

$ r,\ r+M,\ r+2M,\dots, $

so the count is

$ \operatorname{cnt}(r;M)=\left\lfloor\dfrac{N-r}{M}\right\rfloor+1. $

If \(r=0\), then the actual positive integers are

$ M,\ 2M,\ 3M,\dots, $

because \(0\) itself is outside the range, so

$ \operatorname{cnt}(0;M)=\left\lfloor\dfrac{N}{M}\right\rfloor. $

When \(M>N\), every nonzero residue can contribute at most one integer, namely the residue itself, and the zero residue contributes none. That explains the special branch used once the running modulus has become larger than the search interval.

Worked example: from \(210\) to \(2310\)

After processing the primes \(2,3,5,7\), the only allowed residue at each step is \(0\). Therefore every surviving integer must be divisible by

$ 2\cdot 3\cdot 5\cdot 7=210, $

so the survivor set is just the single class \(0 \pmod{210}\).

Now process the prime \(11\). The allowed residues are \(0\) and \(7\). The pair

$ x\equiv 0 \pmod{210},\qquad x\equiv 0 \pmod{11} $

gives \(x\equiv 0 \pmod{2310}\). The pair

$ x\equiv 0 \pmod{210},\qquad x\equiv 7 \pmod{11} $

gives \(x\equiv 1470 \pmod{2310}\), because \(210\equiv 1 \pmod{11}\), so \(t\equiv 7\) and \(x=210\cdot 7\). Thus after prime \(11\), the surviving classes are

$ 0 \pmod{2310}\quad\text{and}\quad 1470 \pmod{2310}. $

If \(N=1470\), the first class contributes nothing because \(2310>N\), while the second contributes the single integer \(1470\). This example shows both the CRT lifting rule and the counting rule once the modulus has crossed \(N\).

How the Code Works

The C++, Python, and Java implementations begin by generating a moderate list of primes. They keep four evolving quantities: the current prime product \(M\), the canonical surviving residues modulo \(M\), the number of integers in \([1,N]\) represented by those residues, and the running value of \(A(N)\).

For each prime \(p\), the implementation computes the inverse of \(M\bmod p\), enumerates the allowed residues \(0,7,14,\dots<p\), and creates every lifted residue modulo \(Mp\). It then counts how many integers up to \(N\) belong to those new classes. The difference between the previous survivor count and the new one is exactly the number of integers whose first failing prime is \(p\), so the code adds \(p\) times that difference to the answer. Once \(M>N\), any lift with a nonzero shift would already exceed \(N\), so those branches are skipped immediately. The process stops as soon as no survivors remain. The C++ implementation uses 128-bit arithmetic for the large products and totals, Python relies on arbitrary-precision integers, and the Java implementation uses big integers where fixed-width arithmetic would overflow.

Complexity Analysis

Let \(R_k\) be the number of surviving residue classes after the \(k\)-th prime has been processed. If the next prime is \(p\), producing the next layer costs

$ O\!\left(R_k\left(\left\lfloor\dfrac{p-1}{7}\right\rfloor+1\right)\right), $

because each active residue is combined with every multiple of \(7\) below \(p\). Counting the next population is linear in the number of new residues, and the prime sieve itself is tiny by comparison.

The important point is that the algorithm never iterates over all integers up to \(N\). Its time and memory depend on the peak number of active residue classes, not on \(10^{17}\) itself. In practice the survivor population collapses quickly, so memory usage stays at \(O(\max_k R_k)\) and the computation remains manageable.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=934
2. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Prime number: Wikipedia - Prime number
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes