11
$\begingroup$

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$:


          DistPrimeFacts
          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$?

$\endgroup$
4
  • 2
    $\begingroup$ math.stackexchange.com/questions/1191698/… $\endgroup$ Commented Oct 5, 2015 at 12:29
  • 2
    $\begingroup$ Although the poster Joe in Carlo's link is of course not Joseph O'Rourke! :-) $\endgroup$ Commented Oct 5, 2015 at 13:53
  • 1
    $\begingroup$ I can't add comments since this account is new, but for those wondering. For sufficiently large numbers, there is a point when 4 overtakes 3 as the peak in the discrete graph. I am referring to an answer in the following question: math.stackexchange.com/a/3547453 $\endgroup$
    – Ubersehen
    Commented Apr 26, 2023 at 2:10
  • $\begingroup$ @Ubersehen I converted it to a comment for you $\endgroup$
    – David Roberts
    Commented Apr 26, 2023 at 3:51

1 Answer 1

18
$\begingroup$

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).

$\endgroup$
7
  • $\begingroup$ Thats very interesting, I initially started looking into this to see if it peaked at e. Thanks for linking this! $\endgroup$
    – Joe
    Commented Oct 6, 2015 at 12:00
  • $\begingroup$ Is there a formula for the distribution seen above? $\endgroup$
    – Joe
    Commented Oct 6, 2015 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$ Commented Oct 6, 2015 at 23:40
  • $\begingroup$ @CarloBeenakker Can you write down the exact distribution which would be useful for us? $\endgroup$
    – Turbo
    Commented Dec 23, 2017 at 4:38
  • 1
    $\begingroup$ This question has gotten a bit old, but is this $0.26$ the Meissel-Mertens constant? $\endgroup$ Commented Jan 13, 2020 at 17:09

You must log in to answer this question.

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