Detailed mathematical approach

Problem Summary

For a given limit \(L\), define \(S(L)\) as the sum of all integers \(n\le L\) such that Euler's totient \(\varphi(n)\) is 5-smooth, meaning that every prime factor of \(\varphi(n)\) belongs to \(\{2,3,5\}\). The target value is \(S(10^{12}) \bmod 2^{32}\), so a direct scan of all \(n\le 10^{12}\) is completely infeasible.

Mathematical Approach

The key observation is that the condition on \(\varphi(n)\) forces a very rigid prime factorization for \(n\). Once that structure is identified, the sum can be reorganized into a much smaller search over 5-smooth numbers and a recursively generated family of admissible prime products.

Step 1: Separate the \(2,3,5\) Part from the Larger Primes

Write

$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$

Euler's product formula gives

$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$

The factors coming from \(2,3,5\) are always 5-smooth:

$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$

So every possible obstruction comes from primes \(p_i>5\).

Step 2: Characterize Which Large Primes Are Allowed

If some prime \(p_i>5\) appears with exponent \(e_i\ge 2\), then the factor \(p_i^{e_i-1}\) divides \(\varphi(n)\). That would force a prime factor larger than \(5\) into \(\varphi(n)\), which is impossible. Therefore every prime \(p>5\) may appear in \(n\) at most once.

Moreover, when \(p>5\) does appear, the factor \(p-1\) divides \(\varphi(n)\). Hence \(p-1\) itself must be 5-smooth. This proves that every valid number has the shape

$n=hq,$

where \(h=2^a3^b5^c\) is a 5-smooth number and \(q\) is a squarefree product of distinct primes \(p>5\) satisfying

$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$

The converse is also true. If \(h\) is 5-smooth and \(q=\prod p\) is a squarefree product of distinct primes with \(p-1\) 5-smooth, then \(h\) and \(q\) are coprime, so

$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$

which is again 5-smooth. Thus the decomposition is exact.

Step 3: Turn the Problem into a Sum over Admissible Prime Products

Let

$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$

be the set of 5-smooth numbers up to \(x\), and define the prefix-sum function

$A(x)=\sum_{h\in\mathcal{H}(x)} h.$

Also define the admissible primes

$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$

Every valid \(n\le L\) is uniquely obtained by choosing a squarefree product \(q\) of distinct primes from \(\mathcal{P}(L)\), then choosing a 5-smooth multiplier \(h\le L/q\). Therefore

$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$

where \(\mathcal{Q}(L)\) is the set of squarefree products \(q\le L\) built from distinct primes in \(\mathcal{P}(L)\), including the empty product \(q=1\).

Pulling \(q\) outside the inner sum gives the main formula

$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$

Step 4: Why Enumerating \(h+1\) Is Enough

The previous step shows that admissible primes are exactly the primes of the form

$p=h+1,\qquad h\in\mathcal{H}(L).$

So instead of searching through all primes up to \(L\), we only generate 5-smooth numbers and test \(h+1\) for primality. This is the decisive reduction: the 5-smooth list is tiny compared with the interval \([1,L]\).

After sorting the 5-smooth numbers, the values \(A(x)\) can be answered by binary search and prefix sums. The remaining task is then to enumerate all feasible subset products \(q\in\mathcal{Q}(L)\), which is done naturally by depth-first search with the pruning rule \(q p\le L\).

Worked Example: \(S(100)=3728\)

For \(L=100\), the 5-smooth numbers are

$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$

The admissible primes \(p=h+1\) are

$\{7,11,13,17,19,31,37,41,61,73,97\}.$

Among their squarefree products, the only ones not exceeding \(100\) are

$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$

The needed prefix sums are

$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$

So the contributions are

$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$

Adding them gives

$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all use the same algorithm.

First, they generate every number of the form \(2^a3^b5^c\le L\) by nested multiplicative loops. The resulting list is sorted, duplicates are removed, and a prefix-sum array modulo \(2^{32}\) is built so that \(A(x)\) can be queried quickly.

Next, for each 5-smooth number \(h\), the implementation tests whether \(h+1\) is prime. It uses fast modular exponentiation and a Miller-Rabin primality test with fixed small bases, which is sufficient for the numeric range of this problem. Every prime \(h+1>5\) is stored as an admissible prime.

Finally, a depth-first search enumerates subset products \(q\) of admissible primes in increasing order. At each recursive state it adds

$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$

to the answer, then tries to append later admissible primes as long as the product stays at most \(L\). Because the search only moves forward through the sorted prime list, each squarefree subset is visited exactly once.

Complexity Analysis

Let \(H=|\mathcal{H}(L)|\), let \(P=|\mathcal{P}(L)|\), and let \(T=|\mathcal{Q}(L)|\), the number of subset products actually visited by the depth-first search. Generating the 5-smooth list takes \(O(H)\) multiplicative steps, while sorting and deduplicating costs \(O(H\log H)\). Building prefix sums is linear in \(H\).

Primality is tested only on the \(H\) candidates \(h+1\), not on every integer up to \(L\). With a fixed-base Miller-Rabin test, this contributes roughly \(O(H\log L)\) modular-arithmetic work. The depth-first search visits each feasible subset product once and performs one binary search on the 5-smooth list per node, so the summation phase costs \(O(T\log H)\).

Thus the algorithm is dominated by the sizes of the 5-smooth list and the feasible subset-product tree, both of which are tiny compared with \(L\) itself. Memory usage is \(O(H+P)\), plus recursion depth proportional to the number of primes currently selected.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=516
2. Euler's totient function: Wikipedia — Euler's totient function
3. Regular numbers / 5-smooth numbers: Wikipedia — Regular number
4. Miller-Rabin primality test: Wikipedia — Miller-Rabin primality test
5. Squarefree integers: Wikipedia — Square-free integer