Alas del Pensamiento: ¿Cuántos ceros hay en el factorial de mil "1000!"?

249

Fórmula:

Cuando 0 < n < 5, f(n!) = 0

Cuando n >=; 5, f(n!) = k + f(k!), donde k = n / 5 (redondeado)

f(1000!) = 200 + f(200!) = 200 + 40 + f(40!) = 240 + 8 + f(8!) = 248 + 1 + f(1) =249

Proceso detallado:

Descripción del problema

Dado el parámetro n (n es un entero positivo), ¡calcule el factorial n de n! El número de "0" al final.

Por ejemplo, ¡5! = 120, el número de "0" contenidos al final es 10; = 3628800, el número de "0" contenidos al final es 20; = 2432902008176640000, el número de "0" contenidos al final es 4.

Fórmula de cálculo

La fórmula de cálculo se proporciona aquí primero y el proceso de derivación se proporciona más adelante.

Sea f(x) el número de "0" contenidos al final del entero positivo x, entonces:

Cuando 0 < n < 5, f(n! ) = 0;

Cuando n >= 5, f(n!) = k + f(k!), donde k = n / 5 (redondeado).

Análisis del problema

Obviamente, para un número grande como el factorial, nos es imposible calcular el resultado y luego contar el número de "0" contenidos al final. Por tanto, hay que analizarlo desde sus características digitales. Comencemos el análisis desde la perspectiva de la factorización.

Consideremos primero la situación general. Para cualquier número entero positivo, si se factoriza, el "0" al final debe descomponerse en 2*5. Aquí cada "0" debe corresponder a un factor "5". Pero tenga en cuenta que en la factorización de un número, el factor "5" no necesariamente corresponde a un "0", porque se necesita un factor "2" para lograr una correspondencia uno a uno.

Volvamos a la pregunta original. Aquí hay primero una conclusión:

Conclusión 1: ¡Para el factorial n de n! , en su factorización, si existe un factor "5", entonces debe corresponder a n! Un "0" al final.

Esta conclusión se demuestra a continuación:

(1) Cuando n < 5, la conclusión está obviamente establecida.

(2) Cuando n >= 5, sea n! = [5k * 5(k-1) * ... * 10 * 5] * a, donde n = 5k + r (0 <= r <= 4), a es un número entero sin factor "5".

Para cada número 5i (1 <= i <= k) en la secuencia 5k, 5(k-1), ..., 10, 5, contiene el factor "5" y está en el intervalo (5(i-1),5i)(1 <= i <= k) Hay números pares en la memoria, es decir, hay un factor "2" en a correspondiente a 5i. Es decir, los k factores aquí son "5" y n. Los k "0" al final corresponden uno a uno.

¡Vamos más allá! Expresado como: n! = 5^k * k! * a (Fórmula 1), donde 5^k representa 5 elevado a la k-ésima potencia. Es fácil de usar (1) y el método iterativo para llegar a la conclusión 1.

¡Lo anterior demuestra el factorial n de n! ¡El "0" y la n al final! El factor "5" en la factorización de tiene una correspondencia uno a uno. Es decir, ¡calcule el factorial n de n! El número de "0" al final se puede convertir para calcular el número de "5" en su factorización.

Sea f(x) el número de "0" contenidos al final del entero positivo x, y g(x) represente el número de factores "5" en la factorización del entero positivo x, luego use La conclusión 1 anterior y la fórmula 1 son:

f(n!) = g(n!) = g(5^k * k! * a) = k + g(k! ) = k + f(k!)

Entonces, la fórmula de cálculo final es:

Cuando 0 < n < 5, f(n!) = 0;

Cuando n >= 5, f(n!) = k + f(k!), donde k = n / 5 (redondeado).

Ejemplo de cálculo

f(5!) = 1 + f(1!) = 1

f(10!) = 2 + f(2! ) = 2

f(20!) = 4 + f(4!) = 4

f(100!) = 20 + f(20!) = 20 + 4 + f(4!) = 24

f(1000!) = 200 + f(200!) = 200 + 40 + f(40!) = 240 + 8 + f(8!) = 248 + 1 + f(1) =249