We know that if $ \displaystyle d(n)= \sum\limits_{d \mid n} 1$, then we have

$$ \sum\limits_{n \leq x} d(n)= x\log{x} + (2C-1)x + \mathcal{O}(\sqrt{x})$$

I have referred Apostol's "Analytic Number theory" and i understood the first half of the proof where the error term is $\mathcal{O}(x)$, but please tell me as to how to improve the error term to $\sqrt{x}$.


2 Answers 2


You can use inclusion/exclusion:

$$\sum_{n\leq x} d(n) = \sum_{mn\le x} 1 = \sum_{m\le \sqrt{x}} \ \sum_{n\le x/m} 1 + \sum_{n\le \sqrt{x}} \ \sum_{m\le x/n} 1 - \sum_{m\le\sqrt{x}} 1 \sum_{n\le\sqrt{x}} 1.$$

Now the first two double sums are the same (with the roles of $m$ and $n$ interchanged). Hence

$$ \sum_{n\leq x} d(n) = 2 \sum_{n\le \sqrt{x}} \Big\lfloor\frac{x}{n}\Big\rfloor - \Big( \big\lfloor\sqrt{x}\big\rfloor \Big)^2$$

where $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$. Now use the fact that $\lfloor x \rfloor=x+O(1)$ to finish the proof. You will have to use the identity

$$ \sum_{n\leq x} \frac{1}{n} = \log x +\gamma + O\Big(\frac{1}{x}\Big)$$

where $\gamma$ is Euler's constant.


I'd post this as a comment, but I don't have the reputation:

There usual route is via the Hyperbola Method: http://myyn.org/m/article/dirichlet-hyperbola-method/


You must log in to answer this question.