# Do most numbers have exactly $3$ 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: (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?

• Fascinating graphs! It’s reasonably intuitive that numbers with a smaller number of factors would outpace those with more factors — because the number of primes is infinite and "evenly spaced" (cf. Prime Number Theorem)… but why it is, in order, 3-2-4-5-1, is a bit of a wonderful mystery. I’m curious what you find out. Feb 12, 2020 at 14:59
• The statements "$P(X \text{ has$3$prime factors})>P(X \text{ has$k$prime factors for some } k\ne3)$", and "$P(X \text{ has$3$prime factors})>P(X \text{ has$k$prime factors})$ for every $k\ne3$" (say, when $X\le N$ for some large $N$) are different. What the question title talks about is more or less the former, while the graph suggests the latter. Feb 12, 2020 at 15:09
• @ SmallestUncomputableNumber: Maybe you can use a double-logarithmic plot, i.e. not plot $(n,\mathit{divisors})$ but instead $(\log n,\log(\mathit{divisors}))$. The current plot tricks you in thinking the growths were linear-ish. Feb 12, 2020 at 15:09
• @emacsdrivesmenuts Great idea, I will add them later Feb 12, 2020 at 15:26
• Notice that we needed to search very far (up to $10^{40}$, but actually something like $10^{24}$ might be sufficient but would not be obvious on the plot), because of the $\log \log n$ term in Erdös–Kac theorem, which grows very slowly (also, here $\log$ denotes the natural logarithm). Feb 13, 2020 at 15:01

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 A$$001221$$'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))$$.

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.

• You can also just estimate the number of integers up to X with at most 2 prime factors, and show this is 0% of all integers. Feb 13, 2020 at 0:24

Just another plot to about $$250\times10^9$$, showing the relative amount of numbers below with x factors (with multiplicity)

Somewhere between $$151,100,000,000$$ and $$151,200,000,000$$ 4 overtakes r3.