# How many numbers divide $n$?

My questions started with a random homework dump from Stack Exchange (sadly closed):

Someone posted code that performs $$n$$ operations for each $$i \in \{1 \dots n\}$$ that divides $$n$$, asking about its overall complexity.

In itself, that question was not very interesting. But I thought it does hold some interesting problem: given $$n \in \mathbb{N}$$, how many numbers divide $$n$$?

Consider the following:

$$\bullet$$ $$D(n) = \{$$number of divisors of $$n$$ $$\}$$

$$\bullet$$ for $$n$$ that is prime, $$D(n) = 2$$ ($$n$$ and $$1$$)

Therefore, there is probably little hope finding a closed expression for $$D(n)$$. How about an asymptotic bound?

$$\mathbf{Lower}$$ $$\mathbf{Bound:}$$

Let $$n$$ be some non-prime natural number.

$$\bullet$$ $$p_i$$ denotes the $$i$$-th prime number

$$\bullet$$ $$\alpha_i$$ denotes the number of times $$p_i$$ occurs in the factorization of $$n$$. For such primes $$p_j$$ that don't occur at all, $$\alpha_j = 0$$

$$\bullet$$ $$p_t$$ denotes the largest prime number that divides $$n$$

The factorization of $$n$$ is given by:

$$n=p_1^{\alpha_1}*p_2^{\alpha_2} *p_3^{\alpha_3} \dots *p_t^{\alpha_t}$$

Example:

the factorization of $$18$$ is given by:

$$18=2^{1}*3^{2}$$

It is clear then, that since for any $$p_i$$, $$p_i \geq 2$$:

$$p_1^{\alpha_1}*p_2^{\alpha_2} \dots p_t^{\alpha_t}\geq 2^{\alpha_1 + \alpha_2 \dots + \alpha_t }$$

Which gives us the lower bound: $$D(n) = \Omega (\log(n))$$

And here is my question: can we find an upper bound for $$D(n)$$? Is there a similar way to prove $$D(n) = O(\log(n))$$, and that the bound is tight?

• – lhf Apr 11 at 18:41

A classical result is that for all $$n$$, $$\sum_{k \leq n} D(k)= n \ln(n) + (2\gamma-1)n + O(\sqrt{n})$$