11
$\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$ 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

6
$\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$
6
  • $\begingroup$ What I understand you are proposing $O(n^{5/12})$ time complexity and $O(n^{1/2})$ space complexity ? $\endgroup$ Mar 19, 2023 at 5:49
  • $\begingroup$ $O(n^{5/6})$ time, at least, for Deléglise & Rivat for the large values. Depending on your flexibility with time you could get the space as low as $O(n^{1/3+\varepsilon})$, I think. $\endgroup$
    – Charles
    Mar 20, 2023 at 4:00
  • $\begingroup$ Well then it wont interest me as I already have $O(n^{2/3})$ time in $O(n^{2/3})$ space. Deleglise Rivat would still interest me as it says it does the same time in only $O(n^{1/3})$ space. $\endgroup$ Mar 20, 2023 at 4:07
  • $\begingroup$ @sibillalazzerini What you can do is pick off the top few values of M and compute them with D-R so you don’t have to sieve as far. This should save space and time. There will be a cutoff where you won’t save any more time; you should go at least this far. Going further will cost you time but improve your space. (There’s another crossover where you won’t even save space anymore but you clearly won’t go that far.) $\endgroup$
    – Charles
    Mar 20, 2023 at 4:12
  • $\begingroup$ I don't understand you Deleglise Rivat $O(n^{5/6})$ time and $O(n^{5/12}) space$ but their paper says it is $O(n^{2/3})$ time and $O(n^{1/3})$ space. there is significant difference between 0.67 and 0.83. Are you account the log factors for that extra part? $\endgroup$ Mar 20, 2023 at 7:06
1
$\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$
3
  • $\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
  • 1
    $\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$ May 20, 2019 at 15:00
  • 1
    $\begingroup$ @PaulCrowley $O(n^{0.25})$ vs $O(n^{0.67})$. I guess too much to ask for. Having said that with lots of memory available and lots of pre-computation allowed nothing is impossible. It all depends on where you want to draw the lines. $\endgroup$ Mar 20, 2023 at 7:42

You must log in to answer this question.

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