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

Question

Problem:

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

This is the oeis series.

My Thoughts:

I need a sublinear algo, possibly something of the order of $n^{3/4}$ or $n^{2/3}$ time. Any algorithm better than $O(n)$ time complexity is welcome. If you can prove sub-linear is not possible you can tell me that as well.

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

My thoughts are in lines of generalising square free counting function. I know efficient ways of counting square free numbers ie $\sum_{k=1}^{n}|\mu(k)\ne0|$ . It uses trick similar to prime counting functions. Since prime counting function can be generalised to get prime summing function, so should be this. Possibly we can do similar generalising for $\sum_{k=1}^{n}|\mu(k)=1|$ and $\sum_{k=1}^{n}|\mu(k)=-1|$ as well. My ideas are still very vague, Needs refining.

Here is a method to sum square free numbers in $O(n^{1/2})$ time. Somehow we would have to now split them into two ie $|\mu(k)=-1|$ and $|\mu(k)=1|$

To summarise:

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

Answer 1

$$f(x)=\sum_{k\le x} k \mu(k), \qquad \sum_{d\le x} d f(x/d)=1$$ It gives $$\qquad \sum_{d=1} d f(x/d) + \sum_{2\le d \le \sqrt x} d f(x/d) + \sum_{\sqrt x \lt d\le x} d f(x/d) =1$$

When $d \in (\sqrt x, x]$ multiple $d$'s result into same $x/d$, to make use of that setting $\lfloor x/d\rfloor=m$ such that $1\le m< \sqrt{x}$

$$f(x)= 1-\sum_{2\le d\le\sqrt{x}} d f(x/d)- \sum_{1\le m< \sqrt{x}} f(m) \sum_{d\le x,\lfloor x/d\rfloor=m} d $$ $x/d\in [m,m+1)$ iff $d\in (\frac{x}{m+1},\frac{x}m]$ ie. $ \sum_{d\le x,\lfloor x/d\rfloor=m} d=\sum_{d=\lfloor x/(m+1) \rfloor+1}^{\lfloor x/m \rfloor} d$ so that $$f(x)=1-\sum_{2\le d\le \sqrt{x}} d f(x/d)- \sum_{1\le m< \sqrt{x}} f(m) \frac{(\lfloor \frac{x}m \rfloor - \lfloor \frac{x}{m+1}\rfloor) (\lfloor \frac{x}m \rfloor + \lfloor \frac{x}{m+1}\rfloor + 1)}2$$ Calling "compute $f$" recursively and storing the intermediate results $r\mapsto f(r)$ gives a $O(x^{1/2})$ algorithm in space and $\sum_{m\le \sqrt{x}} O(\sqrt{m})+\sum_{d\le \sqrt{x}} O((x/d)^{1/2})= O(x^{3/4})$ in number of calls to "compute $f$" and memory accesses to the stored intermediate values.