# 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.

-

## 1 Answer

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].

-

Thank you for the good answer. – J. J. Aug 1 '12 at 16:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9303391575813293, "perplexity_flag": "head"}