9
$\begingroup$

I recently learnt that the expected number of prime factors for an integer $n$ is on the order of $\log\log n$. This was apparently proven by Hardy and Ramanujan.

This led to me wondering what the expected number of (total) factors for a given number is.

I am aware that, if $n=p_1^{\nu_1}p_2^{\nu_2}p_3^{\nu_3}\cdots p_k^{\nu_k}$, then the number of factors of $n$ is $\prod_{i=1}^k\left(\nu_i+1\right)$. I also know that $\displaystyle P(\nu_i=a)=\frac1{p_i^{~a}}$.  Not sure how to proceed, though.

$\endgroup$
4

1 Answer 1

7
$\begingroup$

The trick is to look at the problem upside down. Instead of looking at each integer and wondering how many divisors they have, which can get quite hard, you instead count how many integers in $[1,n]$ have $k$ as a factor, for $1 \leq k \leq n$. As there are about $n/k$ such integers, you can estimate this by

$$\frac{1}{n}\sum_{k=1}^n \#\{j \leq n : k|j\}=\frac{1}{n}\sum_{k=1}^n (\frac{n}{k}+O(1))=(\sum_{k=1}^n \frac{1}{k})+O(1)=\log(n)+O(1),$$

using the estimation $$H_n=\sum_{k=1}^n \frac{1}{k}=\log(n)+O(1).$$

$\endgroup$
4
  • $\begingroup$ I should mention that the result you are talking about can be proved similarly, but instead of summing over all integers less than $n$, you sum over all primes less than $n$. You are then left to estimate $\sum_{p \leq n} 1/p$, which is about $\log\log(n)$ by Mertens' second theorem. $\endgroup$
    – Jonah
    Apr 29, 2021 at 4:06
  • $\begingroup$ That's a nice answer, and presumably we can more rigorously show the number of divisors is $\log n$ because $n\log n-(n-1)\log(n-1)=\log n+(n-1)\log\left(\frac{n}{n-1}\right)=\log n+1+O\left(\frac 1n\right)$. I wonder, is it possible to specify what $O(1)$ equals though? $\endgroup$ Apr 29, 2021 at 4:13
  • $\begingroup$ We have more precisely that $\#\{j \leq n : k|j\}=n/k-\{n/k\}$, where $\{n/k\}$ denotes the fractional part of $n/k$. Also, $H_n=\log(n)+\gamma+O(1/n)$, where $\gamma$ denotes the Euler-Mascheroni constant. So a more precise estimate would be that the average is $(\frac{-1}{n}\sum_{k=1}^n \{n/k\})+\log(n)+\gamma+O(1/n)$. $\endgroup$
    – Jonah
    Apr 29, 2021 at 4:23
  • $\begingroup$ Very cool. Thanks! $\endgroup$ Apr 29, 2021 at 4:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .