10
$\begingroup$

Given some upper bound $n$ is there an efficient way to calculate the following:

$$\sum_{i=1}^n \varphi(i) $$

I am aware that:

$$\sum_{i=1}^n \varphi(i) = \frac 12 \left( 1+\sum_{i=1}^n \mu(i) \left \lfloor \frac ni \right\rfloor ^2 \right) $$

Where:
$\varphi(x) $ is Euler's Totient
$\mu(x) $ is the Möbius function

I'm wondering if there is a way to reduce the problem to simpler computations because my upper bound on will be very large, ie: $n \approx 10^{11} $.

Neither $\varphi(x) $, nor $\mu(x) $, are efficient to compute for a large bound of $n$

Naive algorithms will take an unacceptably long time to compute (days) or I would need would need a prohibitively expensive amount of RAM to store look-up tables.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Have you tried wikipedia? It gives the following formula for this sum $\sum_{i=1}^k \varphi(i) = \dfrac12 \big( 1 + \sum_{i=1}^k \mu(i) \lfloor \frac{n}{i} \rfloor^2 \big) $. $\endgroup$ – Myself Jun 15 '13 at 17:22
  • $\begingroup$ Wolfram Functions gives an asymptotic sum, which may help depending on exactly what you need this for. $\endgroup$ – George V. Williams Jun 15 '13 at 17:24
  • $\begingroup$ you should make your question clear for everybody, who is $\varphi$? I can't understand the question! $\endgroup$ – math_man Jun 15 '13 at 17:50
  • 1
    $\begingroup$ @awashburn: You second equality does not hold. You can't pull M(n) out of the sum. $\endgroup$ – Charles Jun 15 '13 at 18:34
  • 1
    $\begingroup$ Just a crazy thought, but $\sum_{d | n} \varphi(d) = n$. This could possibly be of use. $\endgroup$ – Dylan Yott Jun 15 '13 at 18:54
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

If you can efficiently compute $\sum_{i=1}^n \varphi(i)$, then you can efficiently compute two consecutive values, so you can efficiently compute $\varphi(n)$. Since you already know that $\varphi(n)$ isn't efficiently computable, it follows that $\sum_{i=1}^n \varphi(i)$ isn't either.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Maybe one cannot compute $\phi$ efficiently in general, but if the op is only interested in particular values, like powers of 10, then I see no objection. $\endgroup$ – Myself Jun 15 '13 at 19:05
  • $\begingroup$ An algorithm that computes $\sum_{i=1}^n \varphi(i)$ with efficiency anywhere close to the efficiency with which we can compute $\varphi(n)$ would count as a huge win here. $\endgroup$ – Paul Crowley May 20 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.