Totient Sum

Let $S(n,m) = \sum\phi(n \times i)$ for $1 \leq i \leq m$. ($\phi$ is Euler’s totient function)
You are given that $S(510510,10^6)= 45480596821125120$.

Find $S(510510,10^{11})$.
Give the last $9$ digits of your answer.

This problem is closely related to the property of Euler’s totient function. Euler’s totient function $\phi(n)$ is a function that returns the amount of numbers less than $n$ that are relatively prime to $n$.

However, it’s really hard to compute $S(510510,10^{11})$ directly due to the large bound, even with the Euler’s totient function property. And the problem doesn’t want the whole answer, but the last $9$ digits of $S(510510,10^{11})$. So it’s possible to solve this problem under modulo $10^9$.

In this particular problem, the interesting aspect is the value of n, $510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17$, which is the product of the first seven prime numbers.

This implies that $n \times i$ covers all the numbers from 1 to $n-1$ exactly once when $i$ ranges from 1 to $n-1$. It’s equivalent to the problem to calculate $\sum_{i=1}^{n-1} \phi(i)$.
Since the computation of Euler’s $\phi$ function $\phi(n) = n*(1-\frac{1}{p1})*(1-\frac{1}{p2})*…*(1-\frac{1}{pk})$, where $p1,p2,…,pk$ are the distinct prime factors of $n$ is multiplicative and $1-\frac{1}{p}$ is a unit in $\mathbb{Z}/p^k$, the function $\phi(n)$ is multiplicative in $\mathbb{Z}/p^k$.

So the problem is to compute $\sum_{i=1}^{p^k-1} \phi(i)$ in $\mathbb{Z}/p^k$. And this is equivalent to computing $\frac{p^k*(p^k-1)}{2}$ due to $\phi(i)$ is even for all i in $Z/p^k$.

So in this problem, the base is $10^9$, k=4, and 5. The k=4 part yields the first 6-digit contribution $0000004950$, while the k=5 part yields the last 9-digit contribution $-0004950000$ ($-$ means it’s under modulo $10^9$), so the answer to the last $9$ digits of $S(510510,10^{11})$ is $500049950$.

Computational programming languages like Python, C++, Java, etc, would be extremely useful to solve this kind of problem faster.

More Answers: