93
$\begingroup$

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?

$\endgroup$
7
  • 4
    $\begingroup$ 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. $\endgroup$
    – Kieren MacMillan
    Commented Feb 12, 2020 at 14:59
  • 3
    $\begingroup$ 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. $\endgroup$
    – user1551
    Commented Feb 12, 2020 at 15:09
  • 2
    $\begingroup$ @ 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. $\endgroup$
    – emacs drives me nuts
    Commented Feb 12, 2020 at 15:09
  • $\begingroup$ @emacsdrivesmenuts Great idea, I will add them later $\endgroup$
    – SmallestUncomputableNumber
    Commented Feb 12, 2020 at 15:26
  • 1
    $\begingroup$ 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). $\endgroup$
    – Watson
    Commented Feb 13, 2020 at 15:01

2 Answers 2

Reset to default
96
$\begingroup$

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

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$
    – Kimball
    Commented Feb 13, 2020 at 0:24
21
$\begingroup$

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

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

$\endgroup$
1
  • $\begingroup$ See also my comment above. $\endgroup$
    – Watson
    Commented Feb 16, 2020 at 9:49

You must log in to answer this question.

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