# What is the expected value of the number of factors of a number?

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.

• Are you asking about the divisor function? (see en.wikipedia.org/wiki/Divisor_function and mathworld.wolfram.com/DivisorFunction.html)? Apr 29, 2021 at 3:30
• Yes, I am talking about the divisor function. Apr 29, 2021 at 3:52
• You have $\prod \nu_i+1$.  I believe that should be $\prod \mathbf(\nu_i+1\mathbf)$. Apr 30, 2021 at 19:30
• Right! I didn't realise that the notation was slightly ambiguous. Also thanks for fixing a few errors I made. May 1, 2021 at 3:38

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).$$
• 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. Apr 29, 2021 at 4:06
• 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? Apr 29, 2021 at 4:13
• 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)$. Apr 29, 2021 at 4:23