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$ Oct 5, 2015 at 12:29
  • 2
    $\begingroup$ Although the poster Joe in Carlo's link is of course not Joseph O'Rourke! :-) $\endgroup$
    – Todd Trimble
    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
    Apr 26, 2023 at 2:10
  • $\begingroup$ @Ubersehen I converted it to a comment for you $\endgroup$
    – David Roberts
    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
    Oct 6, 2015 at 12:00
  • $\begingroup$ Is there a formula for the distribution seen above? $\endgroup$
    – Joe
    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$ Oct 6, 2015 at 23:40
  • $\begingroup$ @CarloBeenakker Can you write down the exact distribution which would be useful for us? $\endgroup$
    – Turbo
    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$ Jan 13, 2020 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.