Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
Thank you for the good answer. –  J. J. Aug 1 '12 at 16:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.