¡Encontrar el cero final de n!

Question

Pregunta: Dado un número entero n, encuentre el número de ceros al final de ¡n!

Busqué la solución, fue implementada en C++:

// we are given n, we want to find its n! trailing zeroes

int count = 0;
while(n)
{
  count += n/5;
  n /= 5;
}
  return count;
}

No me entraba en la cabeza por qué tenía que seguir dividiendo por 5 y luego sumando. Aunque esta es una pregunta de programación, dada su naturaleza matemática, creo que es más adecuada para este foro porque tenemos muchos genios de las matemáticas aquí.

Por favor, ayúdenme.

Answer 1

Un 0 al final significa que el número es divisible por 10, es decir, que es divisible por 2 y 5. El número de 0s al final es el mismo que la potencia más alta que se podría escribir para el 10 en una factorización del número, o bien, la potencia sobre el 2 o el 5 en la factorización del primo (tome el mínimo de las dos potencias, por ejemplo, si su factorización da como resultado $2^4\cdot 5^3$ el número de $10$ s que tiene es $3$ ya que se podría reescribir como $2^1\cdot 10^3$ ).

Desde $n!$ es el producto de todos los números menores o iguales a sí mismo y $5>2$ el número de $5$ s nunca superará el número de $2$ s. Por lo tanto, sólo se necesita la energía en el $5$ en la factorización primaria de $n!$

Para encontrarlo, primero hay que ver cuántos múltiplos de $5$ hay $\leq$ n. Entonces el número de múltiplos de $25$ y así sucesivamente. La respuesta correcta viene dada por la suma de todos estos valores ya que cada $5$ añade uno a la potencia, cada $25$ añade $2$ Cada uno de ellos $125$ añade $3$ y así sucesivamente.

Considere $30!$

$5,10,15,20,25,30$ todos contribuyen con un factor de $5$ a $n!$

Pero $25$ contribuye con un extra $5$ .

Por lo tanto, la respuesta es $6+1=7$ ceros para $30!$ .