Detailed mathematical approach

Problem Summary

We need to evaluate

$S(n,m)=\sum_{i=1}^{m}\varphi(ni),$

for \(n=510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\) and \(m=10^{11}\), then report the last 9 digits. A direct loop over \(10^{11}\) terms is impossible, so the solution must exploit the arithmetic structure of \(n\) and the summatory behavior of Euler's totient.

Mathematical Approach

Let

$P=\{2,3,5,7,11,13,17\},\qquad \Phi(x)=\sum_{k\le x}\varphi(k).$

Since \(n\) is squarefree,

$\varphi(n)=n\prod_{p\in P}\left(1-\frac{1}{p}\right)=92160.$

The implementation turns the original sum into a weighted sum of values of \(\Phi\).

Step 1: Use That \(n\) Is Squarefree

Fix an integer \(i\), and write its prime factorization locally as \(p^a\parallel i\). The contribution of each prime to \(\varphi(ni)/\varphi(n)\) depends on whether that prime already divides \(n\).

If \(p\notin P\), then \(p\) is coprime to \(n\), so multiplicativity gives

$\frac{\varphi(np^a)}{\varphi(n)}=\varphi(p^a).$

If \(p\in P\), then \(n\) already contains one factor of \(p\), and because \(n\) is squarefree we get

$\frac{\varphi(np^a)}{\varphi(n)}=p^a.$

Now use the classical identity

$\sum_{j=0}^{a}\varphi(p^j)=p^a.$

Therefore the local factor can be written as

$\frac{\varphi(np^a)}{\varphi(n)}= \begin{cases} \varphi(p^a), & p\notin P,\\ \sum_{j=0}^{a}\varphi(p^j), & p\in P. \end{cases}$

Multiplying these local identities over all prime powers dividing \(i\) yields a restricted divisor sum. If we call an integer \(d\) \(P\)-smooth when all prime divisors of \(d\) lie in \(P\), then

$\boxed{\varphi(ni)=\varphi(n)\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).}$

This is the crucial transformation behind the whole solver.

Step 2: Swap the Order of Summation

Insert the identity above into \(S(n,m)\):

$S(n,m)=\sum_{i=1}^{m}\varphi(ni)=\varphi(n)\sum_{i=1}^{m}\sum_{\substack{d\mid i\\ d\text{ is }P\text{-smooth}}}\varphi\!\left(\frac{i}{d}\right).$

Now write \(i=dk\). For each fixed \(P\)-smooth \(d\le m\), the inner variable \(k\) ranges from \(1\) to \(\left\lfloor m/d\right\rfloor\). Hence

$S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\sum_{k\le m/d}\varphi(k).$

With the summatory totient function \(\Phi\), this becomes

$\boxed{S(n,m)=\varphi(n)\sum_{\substack{d\le m\\ d\text{ is }P\text{-smooth}}}\Phi\!\left(\left\lfloor\frac{m}{d}\right\rfloor\right).}$

So the original problem is reduced to two tasks:

1. enumerate all \(P\)-smooth numbers \(d\le m\);

2. evaluate \(\Phi(x)\) quickly for the quotients \(x=\left\lfloor m/d\right\rfloor\).

Step 3: Enumerate the Relevant Smooth Numbers

Because \(P\) has only seven primes, every relevant \(d\) has the form

$d=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}\le 10^{11}.$

A depth-first search over the exponent choices generates every such value exactly once. This is practical because the smoothness condition is extremely restrictive compared with all integers up to \(10^{11}\).

For the actual parameters, the enumeration contains only \(152751\) smooth numbers. Many of them lead to the same quotient \(\left\lfloor m/d\right\rfloor\), so the implementation deduplicates those quotients before evaluating \(\Phi\).

Step 4: Compute the Summatory Totient Fast

The key identity is

$\sum_{d\mid t}\varphi(d)=t.$

Summing over \(1\le t\le x\) gives

$\sum_{t=1}^{x} t=\sum_{t=1}^{x}\sum_{d\mid t}\varphi(d)=\sum_{u=1}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).$

If we write the triangular number as

$T(x)=\frac{x(x+1)}{2},$

then isolating the \(u=1\) term yields the recursion

$\boxed{\Phi(x)=T(x)-\sum_{u=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{u}\right\rfloor\right).}$

The floor quotient stays constant on intervals. If

$q=\left\lfloor\frac{x}{\ell}\right\rfloor,\qquad r=\left\lfloor\frac{x}{q}\right\rfloor,$

then \(\left\lfloor x/u\right\rfloor=q\) for every \(u\in[\ell,r]\), so the recursion can be blocked as

$\Phi(x)=T(x)-\sum_{\text{quotient blocks}}(r-\ell+1)\,\Phi(q).$

This reduces the work dramatically, because the number of distinct floor quotients is only \(O(\sqrt{x})\). The implementation stores small values in a totient-prefix table and memoizes large recursive calls.

Worked Example

It is helpful to test the formula on a smaller squarefree value, say \(n=6=2\cdot 3\) and \(m=5\). Then \(P=\{2,3\}\), \(\varphi(6)=2\), and the \(P\)-smooth numbers up to \(5\) are

$1,2,3,4.$

Therefore

$S(6,5)=2\left(\Phi(5)+\Phi(2)+\Phi(1)+\Phi(1)\right).$

Since

$\Phi(1)=1,\qquad \Phi(2)=1+1=2,\qquad \Phi(5)=1+1+2+2+4=10,$

we get

$S(6,5)=2(10+2+1+1)=28.$

Direct verification matches:

$\varphi(6)+\varphi(12)+\varphi(18)+\varphi(24)+\varphi(30)=2+4+6+8+8=28.$

How the Code Works

The C++, Python, and Java implementations use the same arithmetic strategy. First they factor \(n\), compute \(\varphi(n)\), and generate every \(P\)-smooth number \(d\le m\). Next they form the quotient list \(\left\lfloor m/d\right\rfloor\), sort it, remove duplicates, and evaluate each distinct \(\Phi(q)\) only once.

For small \(q\), the implementation uses a linear totient sieve and prefix sums up to \(12000000\). For larger \(q\), it applies the quotient-block recursion above and memoizes the results. After all required \(\Phi(q)\) values are available, it sums them with multiplicity, multiplies by \(\varphi(n)\), and obtains \(S(n,m)\).

The implementation also validates itself before attacking \(10^{11}\): it compares against direct summation for several small values of \(m\), and it checks the published checkpoint

$S(510510,10^6)=45480596821125120.$

The final accumulation can be split across multiple threads, but the arithmetic formula itself is unchanged.

Complexity Analysis

Let \(A(m)\) be the number of \(P\)-smooth integers \(d\le m\), and let

$Q(m)=\#\left\{\left\lfloor\frac{m}{d}\right\rfloor : d\le m,\ d\text{ is }P\text{-smooth}\right\}.$

Enumerating the smooth numbers costs \(O(A(m))\). Sorting and deduplicating the quotients costs \(O(A(m)\log A(m))\). Each new summatory-totient value \(\Phi(q)\) is computed by quotient blocking plus memoization, so a single uncached query touches only the distinct floor-division blocks, which is \(O(\sqrt{q})\) in the classical analysis.

For the actual input,

$A(10^{11})=152751,\qquad Q(10^{11})=20313,$

which explains why the method is feasible even though the original sum has \(10^{11}\) terms. Memory usage is dominated by the totient-prefix table, the memoization cache, and the arrays storing the smooth numbers and quotient values.

References

1. Problem page: https://projecteuler.net/problem=432
2. Euler totient function: Wikipedia — Euler's totient function
3. Smooth number: Wikipedia — Smooth number
4. Dirichlet hyperbola method: Wikipedia — Dirichlet hyperbola method
5. Apostol, T. M. Introduction to Analytic Number Theory, Chapters 2-3.