Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is $\sum_{i=1}^n |\{k \in \mathbb{N} \mid k | i\}|$ asymptotically (as a function of $n$)?

(I'm summing, for each of $1,\dotsc,n$, its number of divisors)

Or at least, what's the best upper bound you can find?

share|cite|improve this question
The number of divisors of $n$ is usually denoted $d(n)$ or $\sigma_0(n)$. – Arturo Magidin Aug 16 '11 at 17:55
Does it behave like harmonic sum? – Goog Aug 16 '11 at 17:56
up vote 13 down vote accepted

Let $d(n)$ denote the number of divisors of $n$.

Dirichlet's Asymptotic Formula. (Theorem 3.3 in Tom Apostol's Introduction to Analytic Number Theory) For all $x\geq 1$, we have $$\sum_{n\leq x} d(n) = x \log x + (2C-1)x + O(\sqrt{x}),$$ where $C$ is Euler's constant, $$C = \lim_{n\to\infty}\left(1 + \frac{1}{2} + \frac{1}{3}+\cdots+\frac{1}{n}-\log n\right).$$

The proof involves writing the sum as $$\sum_{n\leq x}d(n) = \sum_{d\leq x} \sum_{q\leq x/d} 1,$$ and interpreting it as counting lattice points in the $qd$ plane; the lattice points with $qd=n$ lie on a hyperbola; then one can get that $$\sum_{q\leq x/d} 1 = \frac{x}{d} + O(1),$$ and from this and the fact that $$\sum_{n\leq x}n^{\alpha} = \frac{x^{\alpha+1}}{\alpha+1} + O(x^{\alpha}),\qquad \text{if }\alpha\geq 0,$$ one derives that $$\sum_{n\leq x}d(n) = x\log x + O(x).$$ The more precise formula uses the symmetry of the corresponding hyperbola along $q=d$. Apostol's book has all the details.

The error term $O(\sqrt{x})$ can be improved: you can see a summary in Wikipedia; best estimate so far is due to Huxley, who proved the error term is $O(x^{(131/416)+\epsilon})$ for all $\epsilon\gt 0$. Hardy and Landau proved that the smallest exponent possible is at least $\frac{1}{4}$.

share|cite|improve this answer
In terms of the lower bound and $\Omega$ results, the best known is due to Soundararajan and states that $$\Delta(x)=\Omega\left(\frac{x^\frac{1}{4}\left(\log x\right)^\frac{1}{4} (\log \log x)^\beta}{\left(\log \log \log x\right)^\frac{5}{8}}\right)$$ where $\alpha=\frac{3}{4}\left(2^\frac{4}{3}-1\right)$. Now, the very interesting thing is that "it is plausible the first three exponents above are optimal." (quote from Montgomery and Vaughns book, Chapter 2 Notes) I remember reading this quite a while ago and finding it very strange. See: – Eric Naslund Aug 18 '11 at 0:29

You can find a good summary in the following Wikipedia article.

The main term in the estimate for $\sum_{i=1}^n d(i)$ is $$n\log n +(2\gamma -1)n,$$ where $\gamma$ is Euler's $\gamma$.

There is a large literature on the error term. Dirichlet got $O(n^{1/2})$, and it is known that one cannot do better than $O(n^{1/4})$.

Note: For a number-theoretic function, this is a fantastically precise estimate. We have a dominant term, $n\log n$, that gives us the asymptotic behaviour. We have also an explicitly known correction term $(2\gamma-1)n$. And, by number-theoretic estimate standards, the error term is quite small compared to $(2\gamma-1)n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.