El número de primos en la factorización de $N!$

Question

¿Existe una aproximación al número de primos en la factorización de $N!$ ?

Por ejemplo:

• Para $N=10$ este número es $15$ .
• Para $N=100$ este número es $239$ .
• Para $N=1000$ este número es $2877$ .
• Para $N=10000$ este número es $31985$ .
• Para $N=100000$ este número es $343614$ .
• Para $N=1000000$ este número es $3626619$ .

Parece que hay un ascenso gradual hacia $4N$ ¿pero se ha demostrado que eso es un límite superior?

Answer 1

Esto no responde completamente a su pregunta, pero es útil saberlo y el argumento puede ser completamente riguroso.

La mayor potencia de un primo $p$ dividiendo $N!$ es $$\left\lfloor \dfrac{N}p \right\rfloor + \left\lfloor \dfrac{N}{p^2} \right\rfloor + \cdots \sim \dfrac{N}{p-1}$$ y el número de primos menores que $N$ es $\sim \dfrac{N}{\log(N)}$ y $\displaystyle \sum_{p \leq N} \dfrac1p \sim \ln(\ln(N))$ y por lo tanto $$\sum_{p \leq N} \dfrac{N}{p-1} \sim N \ln(\ln(N))$$ Por lo tanto, mi posible suposición es $\sim N \ln(\ln(N))$ .

---

Por ejemplo, si se toma $N$ para ser $10^m$ Entonces tenemos la mayor potencia de $2$ dividiendo $10^m$ como $$\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}$$ Del mismo modo, la mayor potencia de $5$ dividiendo $10^m$ como $$\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}$$

Por lo tanto, el número de factores primos de $N = 10^m$ es $$\dfrac{5N}4 - 5^m - 2^{m-2}$$

Answer 2

$4N$ no es un límite superior. Todos los primos $p \leqslant N$ divide $N!$ con multiplicidad

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

y ningún primo mayor divide a $N!$ .

Tenemos $\frac{N}{p}-1 \leqslant m_p(N) < \frac{N}{p-1}$ y así

$$\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}.$$

Desde

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

tenemos $\Omega(N!) \sim N\log \log N$ .