Rápido algoritmos para el cálculo de la inversión de Möbius

Question

Recordar Möbius de la inversión de la fórmula: si tenemos dos funciones de $f,g \colon \mathbf{N} \to \mathbf{N}$ tal que $$g(n) = \sum_{k=1}^n f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$ es válido para cada $n \in \mathbf{N}$, entonces los valores de $f$ puede ser recuperado como $$f(n) = \sum_{k=1}^n \mu(k) g\left(\left\lfloor \frac{n}{k} \right\rfloor\right),$$ donde $\mu(k)$ es la función de Möbius.

Estoy interesado en rápido algoritmos para el cálculo de un único valor de $f(n)$, suponiendo que el $g$ puede ser calculado en $O(1)$ del tiempo.

El mejor algoritmo que conozco es la siguiente: Hay $O(\sqrt{n})$ valores diferentes $\left\lfloor \frac{n}{k} \right\rfloor$, $1 \le k \le n$. Si ya hemos calculado $f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$2 \le k \le n$, luego $$f(n) = g(n) - \sum_{k=2}^n f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$ puede ser calculado en $O(\sqrt{n})$ el tiempo contando las multiplicidades de los términos en la suma. Mediante el cálculo de la $f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$ de mayor a menor $k$ el tiempo total requerido, a continuación, ser$O(n^{3/4})$, mientras que el uso de $O(\sqrt{n})$ espacio.

Yo también estoy interesado en posibles mejoras en el algoritmo anterior, incluso si se reduce el tiempo requerido sólo por un factor constante.

Answer 1

Usted puede mejorar el $O(n^{3/4})$ algoritmo por un factor constante de aproximadamente tres por la informática sólo los sumandos impares de $k$ mediante el uso de la identidad:

$$\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}$$

que se puede obtener restando $g(\frac{n}{2})$$g(n)$. El extraño enfoque únicamente se menciona en [Lehman 1960] (buscar "en la práctica").

Se puede mejorar aún más el tiempo de complejidad a $O(n^{2/3+\epsilon})$ si usted puede calcular el $f(k)$ por cada $k\in \left\{1,..,u \right\}$$O(u^{1+\epsilon})$, como es típico para las funciones aritméticas mediante el uso de un (posiblemente segmentada) tamiz.

Dos referencias para el $O(n^{2/3})$ enfoque son [Pawlewicz 2008] y [Deleglise 1996].