The number of primes in the factorization of $N!$

185 Views Asked by At

Is there an approximation to the number of primes in the factorization of $N!$?

For example:

  • For $N=10$, this number is $15$.
  • For $N=100$, this number is $239$.
  • For $N=1000$, this number is $2877$.
  • For $N=10000$, this number is $31985$.
  • For $N=100000$, this number is $343614$.
  • For $N=1000000$, this number is $3626619$.

There seem to be a gradual ascendant towards $4N$, but has that been proved as an upper limit?

2

There are 2 best solutions below

4
On BEST ANSWER

$4N$ is not an upper limit. Every prime $p \leqslant N$ divides $N!$, with multiplicity

$$m_p(N) = \sum_{k=1}^{\left\lfloor\frac{\log N}{\log p}\right\rfloor} \left\lfloor \frac{N}{p^k}\right\rfloor,$$

and no larger prime divides $N!$.

We have $\frac{N}{p}-1 \leqslant m_p(N) < \frac{N}{p-1}$, and so

$$\sum_{p\leqslant N} \left(\frac{N}{p}-1\right) < \Omega(N!) = \sum_{p\leqslant N} m_p(N) < \sum_{p \leqslant N} \frac{N}{p-1}.$$

Since

$$\sum_{p\leqslant N} \frac{1}{p} \sim \log \log N \sim \sum_{p\leqslant N} \frac{1}{p-1},$$

we have $\Omega(N!) \sim N\log \log N$.

0
On

This does not completely answer your question but is helpful to know and the argument can be made completely rigorous.

The highest power of a prime $p$ dividing $N!$ is $$\left\lfloor \dfrac{N}p \right\rfloor + \left\lfloor \dfrac{N}{p^2} \right\rfloor + \cdots \sim \dfrac{N}{p-1}$$ and the number of primes less than $N$ is $\sim \dfrac{N}{\log(N)}$ and $\displaystyle \sum_{p \leq N} \dfrac1p \sim \ln(\ln(N))$ and hence $$\sum_{p \leq N} \dfrac{N}{p-1} \sim N \ln(\ln(N))$$ Hence, my possible guess is $\sim N \ln(\ln(N))$.


For instance, if you take $N$ to be $10^m$, we then have the highest power of $2$ dividing $10^m$ as $$\dfrac{N}2 + \dfrac{N}{2^2} + \cdots \dfrac{N}{2^m} = \dfrac{N}2 \dfrac{1-1/2^m}{1-1/2} = N - \dfrac{N}{2^m}$$ Similarly, the highest power of $5$ dividing $10^m$ as $$\dfrac{N}5 + \dfrac{N}{5^2} + \cdots \dfrac{N}{5^m} = \dfrac{N}5 \dfrac{1-1/5^m}{1-1/5} = \dfrac{N}4 - \dfrac{N}{4 \cdot 5^m}$$

Hence, the number of prime factors of $N = 10^m$ is $$\dfrac{5N}4 - 5^m - 2^{m-2}$$