¿Simplificación de $\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$?

Question

En la programación de unos contextos, he llegado a través de código a lo largo de estas líneas:

total = 0
for i from 1 to n
    total := total + n / i

Donde la división aquí es la división de enteros. Matemáticamente, esto se reduce a evaluar

$$\sum_{i = 1}^{n}\left\lfloor\, n \over i\,\right\rfloor.$$

This is upper-bounded by $n H_ {n} $ and lower-bounded by $ nH_ {n} - n$ using the standard inequalities for $\texttt{floor}$'s, pero ese límite superior probablemente tiene un boquete grande en el valor verdadero.

¿Hay una manera de obtener un valor exacto para esta suma o encontrar alguna función más simple es asintóticamente equivalente a?

Answer 1

Para el cálculo exacto, una simplificación comienza con la observación

$$ \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor = \sum_{i,j} [1 \leq i] [1 \leq j] [ij \leq n] 1$$

donde $[P]$ es la Iverson soporte: es $1$ si $P$ es cierto, y $0$ si es falso.

De todos modos, el uso de la simetría, se puede romper este a

$$ \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor = -\lfloor \sqrt{n} \rfloor^2 + 2 \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{i} \right\rfloor $$

Esta forma es la mejor para hacer estimaciones aproximadas demasiado, ya que el error de redondeo es una proporción mucho menor de los sumandos.

Answer 2

Ver secuencia de OES A006218 y problema de Dirichlet divisor. Asintóticamente tenemos $$a(n) = n (\log n + 2 \gamma - 1) + O(n^\theta)$ $ donde el valor óptimo de $\theta$ es un problema no resuelto: el mejor resultado en la página de MathWorld es $\theta = 131/416$, por Huxley en el año 2003.

Answer 3

Su suma es también igual a $\sum_{i=1}^n \tau(i)$. Observe si hemos sido capaces de calcular esta suma rápida que también podremos determinar si $n$ primer realmente rápido, por lo que no es muy fácil calcular su suma.