Cálculo eficiente de $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

Question

Me doy cuenta de que probablemente no hay una forma cerrada, pero hay una manera eficiente para calcular la siguiente expresión?

$$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$

Me he dado cuenta de $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor = \left\lfloor\frac{\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} \left\lfloor\frac{n}{k}\right\rfloor}{2}\right\rfloor + \sum_{k=1,\ odd(k)}^n \left\lfloor \frac{n}{k}\right\rfloor$$

Pero no puedo ver una manera fácil de dejar el segundo entrar en una recursividad.

Answer 1

Para ver la cantidad inicial de la secuencia de A006218 de OEIS y la página de la Wikipedia sobre el 'Divisor summatory de la función".

Richard Sladkey del papel 'Una Aproximación Sucesiva Algoritmo para calcular el Divisor Summatory Función' propone evolución de la clásica : $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor=2\sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \left\lfloor \frac{n}{k}\right\rfloor-\left\lfloor\sqrt{n}\right\rfloor^2$$ (tal vez que lo que de esta recursiva...)

Algunas otras referencias :

• Una correspondiente respuesta de Rick Sladkey en la S.E.
• Otro [hilo](triangular representación para el divisor summatory función, $D(x)$ representación-para-el-divisor-summatory-función-dx) con javascript.
• Tao y todos los del papel 'métodos Determinísticos para encontrar los números primos'

Answer 2

Además de Raymond cuidada fórmula, he encontrado el siguiente menos cuidada versión. Se basa en la observación de que después de alrededor de $\sqrt n$ términos, empezamos a ver un montón de valores repetidos. Mirando cuántas soluciones hay a $\lfloor\frac{n}{k}\rfloor=a$ podemos obtener una expresión como la siguiente:

$$\underbrace{\sum_{k=1}^{\lfloor\frac{n}{\lfloor\sqrt n\rfloor-1}\rfloor}\lfloor\frac{n}{k}\rfloor}_\text{Direct calculation of sparse values} + \underbrace{\sum_{a=1}^{\lfloor\sqrt n\rfloor}a(\lfloor\frac{n}{a}\rfloor-\lfloor\frac{n}{a+1}\rfloor)}_\text{Grouped calculation of dense values}$$

Esto es útil si usted necesita para sumar algo más complejo como $\sum_{k=1}^nk^m\lfloor\frac{n}{k}\rfloor$