Fast algorithms for calculating the Möbius inversion

Recall the Möbius inversion formula: if we have two functions $f,g \colon \mathbf{N} \to \mathbf{N}$ such that $$g(n) = \sum_{k=1}^n f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$ holds for every $n \in \mathbf{N}$, then the values of $f$ can be recovered as $$f(n) = \sum_{k=1}^n \mu(k) g\left(\left\lfloor \frac{n}{k} \right\rfloor\right),$$ where $\mu(k)$ is the Möbius function.

I am interested in fast algorithms for calculating a single value $f(n)$, assuming that $g$ can be calculated in $O(1)$ time.

The best algorithm I know of is as follows: There are $O(\sqrt{n})$ different values $\left\lfloor \frac{n}{k} \right\rfloor$, $1 \le k \le n$. If we have already calculated $f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$ for $2 \le k \le n$, then $$f(n) = g(n) - \sum_{k=2}^n f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$ can be calculated in $O(\sqrt{n})$ time by counting the multiplicities of the terms in the sum. By calculating the $f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$ from bigger to lower $k$ the total time required will then be $O(n^{3/4})$ while using $O(\sqrt{n})$ space.

I'm also interested in possible improvements to the above algorithm, even if they reduce the required time just by a constant factor.

Solution 1:

You can improve the $O(n^{3/4})$ algorithm by a constant factor of roughly three by computing only the odd summands of $k$ by using the identity:

$$\begin{array}{lll} f \left( n \right) & = & g \left( n \right) - g \left( \frac{n}{2} \right) - \sum_{3 \leq k \leq n, k \:\mathrm{odd}} f \left( \left\lfloor \frac{n}{k} \right\rfloor \right) \end{array}$$

which can be derived by subtracting $g(\frac{n}{2})$ from $g(n)$. The odd-only approach is hinted at in [Lehman 1960] (search for "in practice").

You can further improve the time complexity to $O(n^{2/3+\epsilon})$ if you can compute $f(k)$ for each $k\in \left\{1,..,u \right\}$ in $O(u^{1+\epsilon})$, as is typical for arithmetic functions by using a (possibly segmented) sieve.

Two references for the $O(n^{2/3})$ approach are [Pawlewicz 2008] and [Deleglise 1996].