An asymptotic property of the divisor counting function

Let \tau(n) be the number of positive divisors of the positive integer n and let \phi(n) be Euler’s function. Then it is easily seen that

\phi(n)+\tau(n)\le n+1

for each n. So

\displaystyle\frac{\phi(n)}{n}+\frac{\tau(n)}{n}\le 1+\frac 1n

holds for all n.

Since there are infinitely many primes,


So it follows that


Therefore, by the sandwich theorem,


i.e., \tau(n)=o(n) as n\to\infty. In layman’s terms, this is saying that the number of divisors of n is small compared to n when n is large. The following plot of \tau(n)/n against n for 1\le n\le 500 captures this nicely.

Screenshot 2015-06-26 03.46.54

So this means, for example, that there are only finitely many positive integers n with more than n/2015 divisors, which I think is pretty neat!


Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s