Calculate $ \sum_{k=1}^{n} k\cdot\varphi(k) $

Question

Problem:

Given $n$, Calculate $ \sum_{k=1}^{n} k\cdot \varphi(k) $

This is the oeis series.

My Thoughts:

Oeis gives a couple of approximate estimates/asymptotics but no real formula, exact closed form for this might not be possible. Any algorithm smarter than calculating $\varphi$ all $n$ times is welcome. My hunch says we might be fine with calculating $\varphi$ something of the order of $n^{1/2}$ times.

You can assume $O(n^{2/3})$ memory is available.

I am also thinking on the lines of reducing the problem to some combinations of $\sum_{i=1}^n \varphi(i)$ as I know a few efficient ways to calculate that

To summarise:

• Expected Time complexity: $O(n^{3/4})$ or better.
• Expected Space complexity: $O(n^{2/3})$ or better.

Answer 1

This equality might help a bit:

$$\sum_{k=1}^{n} k\cdot \varphi(k) \ \ = \ \ \sum_{d \le n}{\mu(d)\cdot d \cdot S\left(\left[\frac{n}{d}\right]\right)}, \tag{1}$$

where $S(k)$ is the sum of the first $k$ squares, and $\mu(d)$ is the mobius function.

You can use the formula

$$S(k) = \frac{k(k+1)(2k+1)}{6}, \tag{2}$$

which is quite fast, but $\mu(d)$ will raise the total time complexity above your $O\left(n^{\frac{3}{4}}\right)$.

As mentioned in the link you included, you can use the sieving by intervals method to calculate values of the Mobius function across an interval.

With each interval being of length $\sqrt{n}$, the total space complexity will be $O\left(n^{\frac{1}{2}}\right)$, and I believe the total time complexity will be around $O\left(n\log(n)\log^2(\log(n))\right)$.

Though I think it would be quite hard if not impossible to beat a time complexity of $O(n^{3/4})$ using this method.

---

Proof of $(1)$:

$$\sum_{k=1}^{n} k\cdot \varphi(k) \ \ = \ \ \sum_{k=1}^{n} k \sum_{d\mid k}{\mu(d)\left[\frac{k}{d}\right]}$$

by the inclusion-exclusion principle. Then by changing the order of summations, we have

$$\sum_{d=1}^{n} \mu(d) \ \sum_{k \le n \\ d\mid k}{k\cdot\left[\frac{k}{d}\right]}$$

$$= \sum_{d=1}^{n} \mu(d) \ \sum_{ad \le n}{(ad)\cdot\left[\frac{ad}{d}\right]}$$

$$= \sum_{d=1}^{n} \mu(d) \cdot d \ \sum_{a \le \frac{n}{d}}{a^2}$$

$$= \sum_{d \le n}{\mu(d)\cdot d \cdot S\left(\left[\frac{n}{d}\right]\right)}$$

Answer 2

Found more powerful way of arranging,

let $F(x)=\sum_{k \le x} k\cdot\varphi(k)$

$$ \sum_{i \le x} i \cdot F(x/i) = x(x+1)(2x+1)/6$$

$$ \implies F(x) = x(x+1)(2x+1)/6 \ - \sum_{2 \le i \le x} i \cdot F(x/i)$$

$$ \implies F(x) = x(x+1)(2x+1)/6 \ - \sum_{2 \le i \le \sqrt x} i \cdot F(x/i) \ - \sum_{\sqrt x \lt i \le x} i \cdot F(x/i)$$

let$\ v=x/i$ $$ \implies F(x) = x(x+1)(2x+1)/6 \ - \sum_{2 \le i \le \sqrt x} i \cdot F(x/i) \ - \sum_{\sqrt {x} \lt (x/v) \le x} (x/v) \cdot F(v)$$

$$ \implies F(x) = x(x+1)(2x+1)/6 \ - \sum_{2 \le i \le \sqrt x} i \cdot F(x/i) \ - \sum_{{1} \lt v \le \sqrt {x}} F(v) \sum_{x/v=i}(x/v) $$

Time is primarily governed by the time to sum inside each $F(x)$. And there are $ \sqrt x $ number of $F(i)$ with small $i$ and $ \sqrt x $ number of $F(i)$ with large $i$
Total time = $ \sqrt 1 + \sqrt 2 + \sqrt 3 + ... + \sqrt{\sqrt x} + \sqrt {x/2} + \sqrt {x/3} + ... + \sqrt{\sqrt{x/(x-1)}}$ = $\int\limits_{1}^{\sqrt x} \sqrt t dt +\int\limits_{1}^{\sqrt x} \sqrt {x/t} dt $ = $O(x^{3/4})$