Factorial y ceros

2016-02-18 2024-05-07 #algorithms #math #post

Introducción

Hoy vamos a platicar acerca de los factoriales, en particular de un problema muy interesante que de primera vista puede parecer muy complicado resolver. Adelante, veamos de que trata esto.

El factorial de un numero n se denota con n! y se define de la siguiente manera:


$$n!= \begin{cases} 1 & \text{si n = 0} \\\\ n(n - 1)!& \text{si n > 0} \end{cases}$$

Por ejemplo 5! = 5 * 4 * 3 * 2 * 1 = 120.

El valor de un factorial es una cantidad que crece extremadamente rápido, incluso para valores de n muy pequeños, por ejemplo 10! = 3628800, para 50! = 30414093201713378043612608166064768844377641568960512000000000000…Esta cantidad es realmente inmensa!. Aquí viene el problema, si se dan cuenta 5! = 120, el cual tiene un cero ( 0 ) al final del numero y además 10! = 3628800 con 2 ceros al final del número resultante, por último 50! tiene 12 ceros al final del número resultante, y aun más, el numero de ceros al final del resultado aumenta cuanto más grande es el valor de n, supongo que si se dieron cuenta, solo por si las dudas lo remarco :).

Un problema

Problema

Dado un numero N, siendo 1 <= N <= 1000000000, calcular el numero de ceros al final del resultado de N!.

Entrada

Un único número entero N, 1 <= N <= 1000000000.

Salida

Un solo valor entero indicando la cantidad de ceros al final del numero resultante de N!.

Ejemplos

Ejemplo 1:
Entrada
Salida
4
0
Ejemplo 2:
Entrada Salida
50
12

Antes de continuar les sugiero que primero le piensen un poco y traten de resolver el problema por ustedes mismos, en serio!

Primeras aproximaciones

Esto último seria algo maravilloso si existiera… Y que creen? SI EXISTE!.

El numero de ceros al final de un entero N en base b es igual al exponente de la máxima potencia de b que divide a N. Por ejemplo, sea N = 14000 en base 10, hay 3 ceros al final del número, la máxima potencia de 10 que divide a 14000 es 1000 = 103. El exponente que al que se eleva 10 para dar 1000 es 3, hay tres ceros al final de 14000.

La cantidad de ceros al final de los factoriales es un caso especial y se calcula como sigue.

"El numero de ceros al final de un numero n en base 10 de n! es simplemente la multiplicidad del factor primo 5 en n!. Esto se puede determinar con este caso especial de la formula de Polignac:


$$f(n) = \sum\_{i=1}^k \left \lfloor \frac{n}{5^i} \right \rfloor = \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + \left \lfloor \frac{n}{5^3} \right \rfloor + \cdots + \left \lfloor \frac{n}{5^k} \right \rfloor$$

Donde k debe ser un valor tal que [latex] 5^{k+1} > n ^{n}[/latex] y . Además es necesario tener en cuenta que [latex]f(n)f(n+1)[/latex] y por lo tanto cuanto mas aumente el valor de n el numero de ceros al final del factorial de n siempre sera mayor o igual a cualquier valor menor que n. Nunca menor!.

Por ejemplo, calculemos la cantidad de ceros al final de 50!.

Un valor para k que cumpla [latex] 5^{k+1} > n,, [/latex] es 2. Entonces [latex] + = 10 + 2 = 12, [/latex].

Ahora una posible solución.

long long z(long long n)
{
    long long zeros = 0;
    long long  k = 5;

    while (k <= n) {
        zeros += n / k;
        k *= 5;
    }

    return zeros;
}

Claro que hay otras formas de solucionar este problema pero creo que esto funciona bien.

La Olimpiada Mexicana de Informática (OMI) cuenta con la OMI Training gate, un portal de entrenamiento con juez en línea donde se puede resolver problemas de tipo olimpiada y ser evaluados al instante en el servidor y devolviendo los resultados en el mismo instante. En este portal se presenta un problema llamado K-Ceros el cual puede ser resuelto con lo que hemos visto en este post. Puedes dirigirte a este sitio y con previo registro tener acceso a gran cantidad de problemas de tipo olimpiada de diferentes niveles de complejidad. Se los recomiendo!

Tip: Para el problema de K-Ceros utilicen una búsqueda binaria para agilizar la busqueda del resultado.

Por cierto, el problema con el que iniciamos el post es una versión simplificada del problema Factorial, tomado de www.codechef.com, un sitio donde puedes resolver problemas de todo tipo con juez en línea. La ventaja de este portal es que permite enviar soluciones en una gran variedad de lenjuajes, aproximadamente 35 lenguajes.

Bueno, hasta aqui con este tema, espero que les halla sido de interes y sobre todo de utilidad. Si te ha sido de utilidad este tema les agradeceria un comentario, ya sea para comentar, corregir o preguntar. Bueno, nos vemos en el próximo post :)!

Código fuente

factorial_zeros.cpp z.cpp

Referencias

  1. http://en.wikipedia.org/wiki/Trailing_zero