Número de dígitos cero en factoriales

Question

Aquí es un enigma que alguien se ha preguntado en una entrevista de trabajo: ¿cuántos cero dígitos hay en $100!$?

Bueno, me encontré con la primera $24$ muy rápido por contar cuántas veces cinco divide $100!$ ($5$ divide $20$ veces y $25$ divide $4$ a veces).

Sin embargo, hay más dígitos cero en la mitad de la serie (estos se pueden encontrar en la mano, escribiendo factorial(100) en sage).

Mi pregunta es si hay una forma inteligente de determinar el número de dígitos cero en $100!$, y más generalmente en $n!$.

Por cierto, esto no afectará a la entrevista de trabajo como fue terminado hace algún tiempo.

Answer 1

Usted puede obtener una muy buena estimación por (a) calcular el número de potencias de diez en la factorial, (b) la estimación del número total de dígitos decimales (usando la aproximación de Stirling), y (c) suponiendo que todas las cifras, excepto los ceros finales son igualmente propensos a tener cualquier valor. Ya que hay un montón de poderes de $2$, el número de ceros finales es igual al número de facultades de cinco, más el número de facultades de veinticinco, etc. $$ T_n=\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{5^{k}}}\right\rfloor. $$ La longitud total estimado por Stirling aproximación es $$ L_n=\log_{10}n!=n\log_{10} n - \frac{n}{\ln 10}+O(\ln n). $$ La combinación de estos, nuestra estimación del número total de ceros es $$ Z_{n}\sim T_n + \frac{1}{10}\left(L_n - T_n\right)=\frac{9}{10}\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{5^{k}}}\right\rfloor+\frac{1}{10}n\log_{10}n-\frac{n}{10\ln 10}+O(\ln n). $$ Este resulta ser bastante buena. El uso de WolframAlpha para obtener los valores exactos: $$ \begin{matrix} \text{n} & \text{Estimate} & \text{Exact} & \text{Abs. Error}\\ \hline 1000 & 481 & 472 & 9\\ 2000 & 1022 & 1025 & 3\\ 4000 & 2166 & 2143 & 23\\ 8000 & 4573 & 4645 & 72 \\ 16000 & 9631 & 9560 & 71 \\ 32000 & 20226 & 20227 & 1 \end{de la matriz} $$ El resultado de $n=32000$ es casualidad preciso...

Answer 2

Usted puede calcular fácilmente el número m de última ceros consecutivos de un factorial n! por $m =floor(n/5) + floor(n/5^2) +...+ foor(n/5^K)+...$ parar, obviamente, cuando se llega a un valor de cero. Para $1000!$ obtenemos : $ 200 + 40 + 8+ 1+ 0 = 249 $ ceros. Tenemos m= 24 ceros para n =100, que es $m/n = 24/100 = 0.24 $ ceros por unidad para n=100, mientras que es 249/1000 = 0.249 ceros por unidad para n=1000; y ·el número de ceros en un factorial aumenta más que en una proporción cuando n aumenta·