Efficient way to compute $\sum_{i=1}^n \varphi(i) $

Solution 1:

You can compute $\mu$ efficiently by sieving on intervals. With $n\approx10^{11},$ intervals of length $10^7$ should work well, taking only a few megabytes. Time needed is $O(n\log\log n)$ and space is proportional to $\sqrt n$ or so.

To improve on this, note that $\lfloor n/i\rfloor$ will be constant on large stretches and so that doesn't need to be computed very often. You can then use fast techniques to compute $M(k)$ for a small number of $k$: $n/2,\ n/3,\ n/4,\ \ldots.$ Time needed is roughly $n^{5/6}$ and space is a bit over $n^{1/3}$ using Deléglise & Rivat. You can use sieving to finish the rest in the same time, though it will need a bit more space ($\sqrt n$ would suffice, $n^{5/12}$ is probably achievable without trouble). Practically speaking you'll probably choose somewhat more memory to speed to computation.

Note that this is sequence A002088 in the OEIS.

Edit: I should also mention sequence A064018 which has $$ \sum_{n=1}^{10^{11}}\varphi(n)=3039635509283386211140 $$ (as computed by the late Donovan Johnson) in addition to sums up to other powers of 10.