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

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}$.

share|cite|improve this question
up vote 10 down vote accepted

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.

share|cite|improve this answer

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

There usual route is via the Hyperbola Method:

share|cite|improve this answer

Your Answer


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