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.

$\endgroup$
10
  • 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, 2013 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, 2013 at 17:24
  • 1
    $\begingroup$ @math_man: That's the usual notation for Euler's totient function. $\endgroup$
    – Charles
    Jun 15, 2013 at 18:00
  • 1
    $\begingroup$ @awashburn: You second equality does not hold. You can't pull M(n) out of the sum. $\endgroup$
    – Charles
    Jun 15, 2013 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, 2013 at 18:54

2 Answers 2

Reset to default
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.

$\endgroup$
0
$\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.

$\endgroup$
2
  • $\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, 2013 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, 2019 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .