0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.