Totient Summatory Function

Applying Dirichlet's Hyberbola method for calculating the Totient summatory function exploits an interesting property of the Totient function. For integer $n$, we have

$\displaystyle\sum\limits_{d|n}\varphi(d)=n$ (or) $\varphi * 1 = n$

Let $f(n)=\varphi(n)$. Then

$F(n)=\displaystyle\sum\limits_{i=1}^n\varphi(i)=\Phi(n)$ and  $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}\varphi(d)=\sum\limits_{i=1}^n i=\dfrac{n(n+1)}{2}$.

Using these values in Dirichlet's Hyberbola method, we get

$\dfrac{n(n+1)}{2}=\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \varphi(i) + \sum_{d=1}^u \Phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) -u^{\text{ }}\Phi\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

Solving for the first term of the right summation,

$\Phi(n)=\dfrac{n(n+1)}{2}-\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \varphi(i) - \sum_{d=2}^u \Phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) +u^{\text{ }}\Phi\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$

So if we memoize our results, we have this beautiful method that enables us to calculate the Totient summatory function. A small hiccup in the above method for calculating $\Phi(n)$ is that you need to precompute the values of $\varphi(k)$ for $k \leq \sqrt{n}$. I have a Mathematica code later along with the timings for reference.

The code takes $70$ seconds to compute $\Phi(10^9)=303963551173008414$, $11$ seconds to compute $\Phi(10^8)=3039635516365908$ and $2$ seconds to compute $\Phi(10^7)=30396356427242$.

But we have another method which will be a bit slower at the expense of not having to precompute the any values. It exploits some of the properties of Euler's totient function and can be generalized to a certain extent. Meanwhile, can you see how we can apply Dirichlet's Hyperbola method to calculate the Mertens function?


Yours Aye
Me