Count the number of prime factors of a number $n$ to include multiplicity, so that $$n=24=2^3 \cdot 3 = 2 \cdot 2 \cdot 2 \cdot 3$$ has $4$ prime factors, and $$n = 6500 = 2^2 \cdot 5^3 \cdot 13 = 2 \cdot 2 \cdot 5 \cdot 5 \cdot 5 \cdot 13 $$ has $6$ prime factors.

The distribution is quite regular. Here it is for $n \le n_\max$, $n_\max=10^7$:

          About a quarter of $n \le 10^7$ have $3$ prime factors.

Q. What is this distribution explicitly? Where is its peak, for $n \le n_\max$?


this variable $\Omega(n)$, the number of prime factors of $n$ counting multiplicity, has for large $n$ a normal distribution with mean [*] $1+\log(\log n)$ and standard deviation $[\log(\log n)]^{1/2}$; see, for example, Prime Numbers and Computer Methods for Factorization, page 167 [first edition], page 159 [second edition].

[*] more precisely, this additive constant 1 should be replaced by $1.03465\ldots$ as calculated by Knuth and Trabb-Pardo (appendix A); incidentally, if we don't count multiplicities the normal distribution has mean $0.26+\log(\log n)$ with the same standard deviation $[\log(\log n)]^{1/2}$, so the only difference is a slight displacement of the whole curve.

--- update 2020, in response to query:

the "0.26" number is defined as $$c_1= \gamma+\sum_{p\;\text{prime}}\biggl(\log(1-1/p)+\frac{1}{p}\biggr)= 0.261497212847643$$ while the "1.03" number is defined as $$c_2=\gamma+\sum_{p\;\text{prime}}\biggl(\log(1-1/p)+\frac{1}{p-1}\biggr)= 1.034653881897438$$ The number $c_1$ is known as the Meissel-Mertens constant. Both $c_1$ and $c_2$ are referred to as Hadamard-de la Vallée-Poussin constants (see also this MathWorld entry).

  • $\begingroup$ Thats very interesting, I initially started looking into this to see if it peaked at e. Thanks for linking this! $\endgroup$ – Joe Oct 6 '15 at 12:00
  • $\begingroup$ Is there a formula for the distribution seen above? $\endgroup$ – Joe Oct 6 '15 at 23:24
  • $\begingroup$ @Joe --- sure, when $n$ goes to infinity it is a Gaussian with the mean and variance indicated in the answer; $\endgroup$ – Carlo Beenakker Oct 6 '15 at 23:40
  • $\begingroup$ @CarloBeenakker Can you write down the exact distribution which would be useful for us? $\endgroup$ – 1.. Dec 23 '17 at 4:38
  • 1
    $\begingroup$ This question has gotten a bit old, but is this $0.26$ the Meissel-Mertens constant? $\endgroup$ – Sylvain JULIEN Jan 13 '20 at 17:09

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.