An approximation for the divisor-counting function

217 Views Asked by At

Let $d(x)=\sum_{a|x} 1$, and now, imagine that the probability of $n$ dividing $x$ is $1 \over n$, being $n$ in the range $1\leq n\leq x$, so, we can say that: $$d(x)\approx\sum_{k=1}^x{1\over k}$$ Now, my question is, can someone prove, or has someone already proved that $d(x)\sim\sum_{k=1}^x{1\over k}$? Sorry if this is a stupid question.

1

There are 1 best solutions below

1
On BEST ANSWER

This heuristic needs a little extra argument, because the various events are not independent. For example, given that $2n$ divides $x$, the probability that $n$ divides $x$ is $1$ and not $1/n$. There are also relations "in the other direction", e.g. if $x$ has no divisors less than $\sqrt{x}$ then it is already prime.

From the Wikipedia, it looks like $\log(n)$ is a bit of an underestimate for the lim sup. https://en.wikipedia.org/wiki/Divisor_function#Growth_rate

(The lim inf is clearly 2 as there are infinitely many primes.)