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:
Sum of Squares of Unitary Divisors
Range Flips
Square Space Silo

Share:

Recent Posts

Mathematics in Cancer Treatment

How Mathematics is Transforming Cancer Treatment Mathematics plays an increasingly vital role in the fight against cancer mesothelioma. From optimizing drug delivery systems to personalizing

Read More »