77
$\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$
  • 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 Feb 12 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 Feb 12 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 Feb 12 at 15:09
  • $\begingroup$ @emacsdrivesmenuts Great idea, I will add them later $\endgroup$ – SmallestUncomputableNumber Feb 12 at 15:26
  • $\begingroup$ @SmallestUncomputableNumber: For the current range, not much will change, but you have more room for bigger values. $\endgroup$ – emacs drives me nuts Feb 12 at 15:32
87
$\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) ~ 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$
  • 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 Feb 13 at 0:24
16
$\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 3.

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

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.