Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem 1. Let $d(k)$ denote the number of divisors of $k\in\mathbb{N}$. Prove that: $$\sum_{k=1}^{n}d(k)=n\ln n +O(n)$$

Problem 2. Show estimation below: $$\sum_{k=1}^{n}\phi(k)=\frac{3}{\pi^2}\cdot n^2+O(n\log n)$$ where $\phi$ is Euler's totient function of course.

I just started having fun with asymptotics and can't manage with these two. They seem very interesting, because this is the first time I've seen asymptotics and number theory together (I know, I haven't seen too much of math, yet) and I'm very curious how these problems can be solved. They also made me wonder if is there any asymptotic estimation for sum with another interesting function: $\sum_{k=1}^{n}\sigma(k)$, where $\sigma(k)$ is the sum of divisors of $k$?

share|improve this question
For $\sum_{1}^n d(k)$, note that $1$ is a divisor of $n$ numbers between $1$ and $n$, and $2$ is a divisor of about $\frac{n}{2}$ numbers, and $3$ is a divisor of about $\frac{n}{3}$ numbers, and so on. So our sum is about $n+\frac{n}{2}+\frac{n}{3}+\cdots+ \frac{n}{n}$. That takes care of things, since at each stage the "about" is off by at most $1$, adding up to at most $n$. –  André Nicolas Aug 23 '12 at 19:41
For the second problem, you are just counting the number of coprime pairs $1\leq a < b \leq n$. This problem has appeared on math.se before, e.g. math.stackexchange.com/questions/64498/…. –  Sean Eberhard Aug 23 '12 at 23:32

2 Answers 2

up vote 2 down vote accepted

Number theoretic functions such as the divisor function $d(k)$ jump around quite a bit. Summation often makes the behaviour much smoother. The most familiar example is the function $f(k)$ which is $1$ if $k$ is prime, and $0$ if it is not. Then $\sum_1^n f(k)$ is asymptotically equal to $\frac{n}{\log n}$.

Similarly, $\sum_1^n d(k)$ is well-behaved. The beginnings of the analysis are straightforward. But there is a large literature on the fine details, stretching from the nineteenth century to now.

In the numbers $1$ to $n$, the divisor $1$ occurs $n$ times. The divisor $2$ occurs exactly $\lfloor n/2\rfloor$ times. The divisor $3$ occurs
$\lfloor n/3\rfloor$ times, and so on. Thus $$\sum_1^n d(k)=n+ \left\lfloor \frac{n}{2}\right\rfloor+ \left\lfloor \frac{n}{3}\right\rfloor+\cdots +\left\lfloor \frac{n}{n}\right\rfloor.$$ If we replace $\lfloor n/i\rfloor$ by $n/i$, we make an error of at most $1$ in each term, so $$\sum_1^n d(k)=n+ \frac{n}{2}+ \frac{n}{3}+\cdots + \frac{n}{n}+O(n).$$ By comparing the sum with an integral, one can show that there is a constant $\gamma$, the Euler-Mascheroni constant such that $$\lim_{n\to\infty} \left(1+\frac{1}{2}+\cdots+\frac{1}{n}\right)-\log n=\gamma.$$ It follows that $$\sum_1^n d(k)=n\log n +O(n).$$ Much more is known! The main term is, as we saw, $n\log n$. But a more detailed analysis, that goes back to Dirichlet, shows that $$\sum_1^nd(k)=n\log n +(2\gamma-1)n+O(n^{1/2}).$$

share|improve this answer

$$\sum_{k=1}^n\sigma(k)=\pi^2n^2/12+O(n\log n)$$ This is Theorem 324 in Hardy and Wright, An Introduction to the Theory of Numbers, a book dear to the hearts of Number Theorists worldwide. The proof is not too difficult, but a bit too long for me to want to type it out here.

share|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.