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.
