¿Qué es $\sum_{i=1}^n |\{k \in \mathbb{N} \mid k | i\}|$ asintóticamente (como una función de la $n$)?
(Estoy sumando, para cada una de las $1,\dotsc,n$, su número de divisores)
O al menos, ¿cuál es la mejor cota superior se puede encontrar?
Respuestas
¿Demasiados anuncios?
Deje $d(n)$ denotar el número de divisores de a $n$.
Dirichlet de la Fórmula Asintótica. (Teorema 3.3 en Tom Apostol de la Introducción a la Teoría Analítica de números) Para todos los $x\geq 1$, tenemos $$\sum_{n\leq x} d(n) = x \log x + (2C-1)x + O(\sqrt{x}),$$ donde $C$ es la constante de Euler, $$C = \lim_{n\to\infty}\left(1 + \frac{1}{2} + \frac{1}{3}+\cdots+\frac{1}{n}-\log n\right).$$
La prueba implica la escritura de la suma como $$\sum_{n\leq x}d(n) = \sum_{d\leq x} \sum_{q\leq x/d} 1,$$ y la interpretación es como contar el entramado de puntos en la $qd$ plano, el entramado de los puntos de con $qd=n$ acostará sobre una hipérbola; luego, uno puede conseguir que $$\sum_{q\leq x/d} 1 = \frac{x}{d} + O(1),$$ y a partir de esto, y el hecho de que $$\sum_{n\leq x}n^{\alpha} = \frac{x^{\alpha+1}}{\alpha+1} + O(x^{\alpha}),\qquad \text{if }\alpha\geq 0,$$ una deriva que $$\sum_{n\leq x}d(n) = x\log x + O(x).$$ La más precisa de la fórmula utiliza la simetría de la hipérbola correspondiente a lo largo de $q=d$. Apostol del libro tiene todos los detalles.
El término de error $O(\sqrt{x})$ puede ser mejorado: se puede ver un resumen en Wikipedia; mejor estimación es, hasta ahora, debido a Huxley, que demostró que el término de error es: $O(x^{(131/416)+\epsilon})$ todos los $\epsilon\gt 0$. Hardy y Landau demostrado que el menor exponente es posible, al menos,$\frac{1}{4}$.
Oli
Puntos
89
Usted puede encontrar un buen resumen en el siguiente artículo de la Wikipedia.
El término principal en la estimación para $\sum_{i=1}^n d(i)$ es $$n\log n +(2\gamma -1)n,$$ donde $\gamma$ es de Euler $\gamma$.
Hay una gran cantidad de literatura sobre el término de error. Dirichlet consiguió $O(n^{1/2})$, y se sabe que uno no puede hacer mejor que $O(n^{1/4})$.
Nota: Para un número de la teoría de la función, esta es una fantástica estimación precisa. Tenemos una dominante plazo, $n\log n$, que nos da el comportamiento asintótico. Tenemos también un explícitamente conocido término de corrección de $(2\gamma-1)n$. Y, por el número de la teoría de la estimación de las normas, el término de error es muy pequeño en comparación con $(2\gamma-1)n$.
