8
$\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$
11
$\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.

$\endgroup$
  • $\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$ – Brout Dec 23 '17 at 4:38

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.