If $\pi_k(n)$ is the cardinality of numbers with k prime factors (repetitions included) less than or equal n, the generalized Prime Number Theorem (GPNT) is:

$$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln n)^{k-1}}{(k-1)!}.$$

The qualitative appearance of the actual distribution of $\pi_k(n)$ for k = 1,2,3,..., agrees very well with the GPNT, for numbers $n$ within reach of my laptop. But I noticed that as $n$ and $k$ get large, "most" of the numbers less than $n$ seem to have relatively few factors.

Writing $n = 2^m$ and replacing $k$ by $x$ we can graph

$$f(x) =\frac{2^m (\ln\ln 2^m)^{x-1}}{\ln 2^m (x-1)!}$$

from $x = 1$ to $m$ (since no number will have more than m factors) and see that for relatively small fixed $m$, most of the area under the curve f is is contained in a steep bell-shaped curve on the far left of the image.

I take this to suggest that as we consider very large sets, $S_m = \{ 1,2,3,...,2^m\},$ almost all elements of these sets have a "very small" number of factors (including repetitions).

Can this idea be (or has it been) quantified? The phrase "very small" is frustrating, and I think we might be able to say something more concrete about, for example, concentration of the proportion of area as a function of x and m...? Thanks for any suggestions.

Edit: the answer Eric Naslund gave below is splendid and I won't neglect to accept it. In response to the answer, I wonder if there is any reason not to be able to get something like that answer from the expression $f(x)$?

After all, $f(x)$ appears to be a Poisson-like curve with a mean near the average number of prime factors. If I let m = 100 and then 500 (i.e., we're using $2^{100},2^{500}$), $f'(x) = 0$ at $x \approx 4.73, 6.34$, respectively, while $\ln\ln 2^m$ is respectively 4.23, 5.84. If f is a valid expression for the asymptotic behavior of $\pi_k(n)$, wouldn't we expect it to give us this additional information? Can we not prove it?

  • 1
    $\begingroup$ Regarding your second question, I would like to point out that $\log \log N$ grows extremely slowly. To emphasize this, it has been said that $\log \log N$ goes to infinity, but has never been observed to do so. In fact it grows so slowly that $\log \log 10^{20}$ is less then $4$, and $10^{20}$ is likely a much larger number then the ranges in your computations. Because of this, numerical computations are likely to be extremely unreliable, and potentially very far from the asymptotic truth. $\endgroup$ – Eric Naslund Jul 8 '12 at 20:33

This is a great question. There has been a lot of work done regarding the distribution of the number of prime factors function, and the most famous of which is the Erdos Kac Theorem, which states that the number of prime factors is in fact normally distributed.

We can ask, what is the average number of prime factors for integers in the interval $[1,N]$? Lets define the function $\omega(n)=\sum_{p|n} 1$ to be the number of distinct prime factors of $n$.

In 1917, Hardy and Ramanujan used the circle method to prove that almost all integers in the interval $[1,N]$ asymptotically have $\log \log N$ prime factors. Specifically, if $$\mathcal{E}_N=\{n\leq N: |\omega(n)-\log \log N|>(\log \log N)^{3/4}\},$$ then $|\mathcal{E}_N|=o(N)$. In 1934 Turan gave an alternative proof of this by showing that both the mean and variance of $\omega(n)$ are equal to $\log \log N$. Specifically, Turan proved that $$\frac{1}{N}\sum_{n\leq N}\omega (n) =\log \log N(1+o(1))$$ and that $$\frac{1}{N}\sum_{n\leq N}(\omega (n)-\log \log N)^2 =\log \log N(1+o(1)).$$

Now, here is where things become really interesting. Since we know the mean and variance, lets normalize and look at the function $$\frac{\omega(n)-\log \log n}{\sqrt{\log \log n}}.$$ We can ask, how is this distributed? In 1940, Erdos and Kac proved that $\omega(n)$ is normally distributed. That is, the number of prime factors function behaves like the normal distribution with mean $\log \log N$ and variance $\log \log N$. Specifically, for any fixed real numbers $a,b$, we have that$$\frac{1}{N}\left|\left\{n\leq N:\ a\leq\frac{\omega(n)-\log \log n}{\sqrt{\log \log n}}\leq b\right\}\right|=\frac{1}{\sqrt{2\pi}}\int_a^b e^{-x^2/2}dx +o(1).$$

  • $\begingroup$ This is a great answer, and a great question. I was wondering if anything is known about the (expected/average/etc) order of the maximal prime divisor of an integer n? Could you recommend some references on this? $\endgroup$ – gen Feb 15 at 22:06
  • 1
    $\begingroup$ @gen: For the average of the largest prime factor less than $n$, see this paper: kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/n81/n81.pdf $\endgroup$ – Eric Naslund Mar 17 at 21:13

I am not quite sure that I understand exactly what you're asking, but I think that some of the following points may shed some light on the matter.

Suppose we fix $n$ and let $k$ vary. Studying $\pi_k(n)/n$ is then equivalent to looking at the distribution of the number of prime factors of integers up to $n$ (by the way, this turns out not to be very sensitive to the distinction between "with repetition" and "without repetition").

We have to be a bit careful as the asymptotic for $\pi_k(n)$ is intended for $k$ fixed and $n$ growing (but we can still use it as long as $k$ grows sufficiently slowly with $n$). With that caveat in mind, the approximate distribution given by GPNT can be rewritten as:

$$\frac{\pi_{k+1}(n)}{n} \approx \frac{\lambda^{k} e^{-\lambda}}{k!},\quad k=0,1,2,\ldots$$

where $\lambda = \log \log x$, and I have shifted the value of $k$ by 1. By rewriting it this way, we can recognize the right hand side exactly as a Poisson distribution with parameter $\lambda = \log \log x$.

Loosely interpreted, every number (above 1) is guaranteed to have at least one prime factor, but the additional primes beyond that behave Poissonly with a rate of $\log \log x$. The peak of any Poisson distribution always occurs at $\lambda$. You don't need to take derivatives to see this, just look at the ratio of the $k-1$ and $k$ terms:

$$\frac{\lambda^k e^{-\lambda}}{k!} \cdot \frac{(k-1)!}{\lambda^{k-1} e^{-\lambda}} = \frac{\lambda}{k}.$$

So clearly the Poisson distribution is increasing in $k$ for $k < \lambda$ and decreasing for $k > \lambda$, and the peak occurs at $\lfloor\lambda\rfloor$. Moreover, it is well-known (see the linked Wikipedia article) that the normal distribution with equal mean and variance $\lambda$ approximates the Poisson distribution when $\lambda$ is large. Perhaps this explains the bell curve you observed.

Finally, note that equal mean and variance $\log \log x$ is precisely the situation that arises from the Erdős-Kac theorem in Eric Naslund's answer, although let me reiterate that I am deliberately ignoring the relative sizes of $n$ and $k$ for which these separate facts are known to be true.


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.