Cantidad de ceros al final de un factorial

Un número n (bah, estrictamente el numeral asociado al número n pero vamos a ignorar esa distinción…) termina en k ceros si y solo si puede escribirse como

n = m \cdot 10^k

siendo m un entero no divisible por 10. Un entero es divisible por 10 si y solo si es divisible por 2 y por 5 por lo que, si 5 o 2 no aparecen como factores primos de m, sabremos que n termina con k ceros.

Suponiendo que la descomposición en factores primos de n toma la forma

n = 2^a3^b5^c7^d...

podemos ver que k será min(a, c), ya que de ese modo quedarán o bien 2s o bien 5s como factores primos de m. Esto nos permite reducir la determinación de la cantidad de ceros al final de n! a averiguar la multiplicidad de 2 y de 5 como factores primos de n!.

Como el factorial de n no es más que el producto de los números desde 1 hasta n y los múltiplos de un factor primo k están separados por un intervalo k, sabemos que habrá \lfloor n/k \rfloor múltiplos de k dentro de n!. Esto podría llevarnos a pensar que la multiplicidad de k en n! será \lfloor n/k \rfloor, pero esto omitiría la contribución extra realizada por los múltiplos de las potencias de k.

Teniendo esto en cuenta, la multiplicidad de k como factor primo de n! estará dada por

\displaystyle \sum_{i=0}^\infty \left\lfloor \frac{n}{k^i} \right\rfloor,

una suma que siempre converge ya que consta de una cantidad finita de términos.

Puede verse que la cantidad de factores 2 será siempre mayor o igual que la de factores 5 (la suma es mayor o igual término a término), por lo que alcanzará con calcular la cantidad de factores 5 en n! para conocer la cantidad de ceros al final:

\text{cantidad de ceros al final de } \displaystyle n! = \sum_{i=0}^\infty \left\lfloor \frac{n}{5^i} \right\rfloor.

Escribiendolo como una función en Python:

def fact_num_zeros(n):
    if n > 0:
        return n // 5 + fact_num_zeros(n // 5)
    else:
        return 0

Hacemos un par de funciones adicionales para revisar los resultados:

def factorial(n):
    acum = 1
    for i in range(1,n+1):
        acum *= i
    return acum

def num_zeros_at_end(a):
    num_zeros = 0
    while True:
        a, m = divmod(a, 10)
        if m != 0:
            break
        num_zeros += 1
    return num_zeros

Probando con 10000!:

>>> num_zeros_at_end(factorial(10**4))
2499
>>> fact_num_zeros(10**4)
2499

Coincide internamente y con el resultado de Demian… Ahora con 1016!:

>>> fact_num_zeros(10**16)
2499999999999996L

Como puede observarse, la cantidad es “algo” mayor que 1000, por lo que la respuesta dada por Demian era correcta 😀

Advertisements

2 thoughts on “Cantidad de ceros al final de un factorial

  1. Demian says:

    Yeahh! No estaba loco! (?)

    Muy buena la demostración. Quedó re prolija jeje (en especial la forma de expresar la multiplicidad de un factor primo de n!)

    [mode_programmer on]
    Y… evidentemente python se presta para estas cosas mucho mas que java jajja.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s