método de los divisores

Question

Tengo una secuencia: $1,3,5,8,10,14,16,20,23,27,\dots$

Sé que la relación recursiva es:

$$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.}$$

¿Cómo resolver esta relación recursiva en $O(n^{0.5})$ tiempo? Tengo que escribir un programa para ello, y $n$ puede ser tan grande como $10^9$. Así, algunos adecuadas precomputation y prestorage está permitido, siempre que se cumpla (memoria y tiempo prudente) con el rango de $n$.

Answer 1

Buscas $p_n = \sum_{k=1}^n d(k)$ donde $d(k)$ es el número de divisores de a $k$.

Este papel de reclamaciones de un algoritmo que se ejecuta en $O(n^{1/3})$ tiempo y $O(\log n)$ espacio. Ver también los métodos Determinísticos para encontrar los números primos por Tao, Croot Enfermo y Helfgott surgido de un Polímata del proyecto.

Tenga en cuenta que la fórmula (4) en el primer enlace da un simple $O(\sqrt n)$ algoritmo de:

$$p(n) = 2\sum_{k=1}^{\lfloor\sqrt{n} \rfloor} \left\lfloor\frac{n}{k} \right\rfloor- \lfloor\sqrt n \rfloor^2$$