Do most numbers have exactly 33 prime factors?

In this question I plotted the number of numbers with n prime factors. It appears that the further out on the number line you go, the number of numbers with 3 prime factors get ahead more and more.

The charts show the number of numbers with exactly n prime factors, counted with multiplicity:
enter image description here
enter image description here
(Please ignore the ‘Divisors’ in the chart legend, it should read ‘Factors’)

My question is: will the line for numbers with 3 prime factors be overtaken by another line or do ‘most numbers have 3 prime factors’? It it is indeed that case that most numbers have 3 prime factors, what is the explanation for this?

Answer

Yes, the line for numbers with 3 prime factors will be overtaken by another line. As shown & explained in Prime Factors: Plotting the Prime Factor Frequencies, even up to 10 million, the most frequent count is 3, with the mean being close to it. However, it later says

For n = 10^9 the mean is close to 3, and for n = 10^{24} the mean is close to 4.

The most common # of prime factors increases, but only very slowly, and with the mean having “no upper limit”.

OEIS A001221‘s closely related (i.e., where multiplicities are not counted) Number of distinct primes dividing n (also called omega(n)) says

The average order of a(n): \sum_{k=1}^n a(k) \sim \sum_{k=1}^n \log \log k.Daniel Forgues, Aug 13-16 2015

Since this involves the log of a log, it helps explain why the average order increases only very slowly.

In addition, the Hardy–Ramanujan theorem says

… the normal order of the number \omega(n) of distinct prime factors of a number n is \log(\log(n)).

Roughly speaking, this means that most numbers have about this number of distinct prime factors.

Also, regarding the statistical distribution, you have the Erdős–Kac theorem which states

… if ω(n) is the number of distinct prime factors of n (sequence A001221 in the OEIS, then, loosely speaking, the probability distribution of

\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}

is the standard normal distribution.

To see graphs related to this distribution, the first linked page of Prime Factors: Plotting the Prime Factor Frequencies has one which shows the values up to 10 million.

Attribution
Source : Link , Question Author : SmallestUncomputableNumber , Answer Author : Yassir

Leave a Comment