Contar ceros finales de números factoriales en cualquier sistema numérico

¿Cómo puedo calcular el número de ceros finales del factorial de un número en un determinado sistema de números?

Veamos el caso cuando estamos en el décimo sistema de números, y luego veamos cómo podemos generalizar esto en una solución universal. Se nos da el número N y para su factorial necesitamos encontrar el número de ceros finales. La solución será bastante simple: la suma:

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ... 

Podemos generalizarlo en tal fórmula:

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}.$$

¿Por qué 5? Es simple El cero final se obtiene solo cuando el número tiene 10 en el factorial, por lo tanto, contando el número de decenas en el factorial, descubrimos el número de ceros finitos.

¿Por qué en el ejemplo anterior dividimos por 5? Como se puede obtener 10 multiplicando 5 por 2. Por lo tanto, la solución completa tendrá dos fórmulas:

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}$$

y

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 2 ^ i}.$$

Pero, razonando lógicamente, sabemos que la primera cantidad será menor, por lo que solo necesitamos calcularla (se pueden encontrar más detalles aquí ).

Solución a nuestro problema.

Para calcular los ceros finales del factorial de un número en un sistema numérico específico, compilé el algoritmo a continuación:

1. Factoriza el número B del sistema numérico.
2. Divida el número N por cada factor primo único K, multiplicando K por sí mismo hasta $$$N \ sobre K$será más de uno, mientras se redondea cada resultado a un entero más pequeño.
3. Si, al expandir el número del sistema de números, obtenemos varios factores primos idénticos K, entonces deberíamos dividir el resultado anterior por el número de K. idénticos
4. De todas las divisiones de N por cada factor único K, elija el cociente más pequeño, que será nuestra respuesta.

Lo mostraré con un ejemplo.
Sea el número N = 5, el sistema de números B = 12. ¡Factorial 5! = 120, y 120 en el sistema 12 es A0. Vemos que en un sistema de números finitos el factorial del número original tiene un cero. Si descomponemos 12 en factores primos, obtenemos 2, 2, 3. Tenemos dos números únicos: 2 y 3. Siguiendo nuestro algoritmo, cumpliremos el punto 2 con el número 2.

$$

$${5 \ over 2} + {5 \ over 4} + {5 \ over 8} + ... = 2 + 1 + 0 + ... = 3.$$

Pero el deuce se reunió dos veces en la descomposición de 12, por lo que dividimos el resultado final entre 2 y redondeamos a un número entero más pequeño. Como resultado, obtenemos 1.

Hacemos lo mismo con 3:

$$

$${5 \ over 3} + {5 \ over 9} + ... = 1 + 0 + ... = 1.$$

Por lo tanto, hemos obtenido dos cocientes de divisiones del número N por factores primos del número del sistema numérico. Ambos son iguales a 1, por lo que no tenemos que elegir el más pequeño y solo damos la respuesta: 1.

Considere otro ejemplo.

Sea el número N = 16, el sistema de números B = 16. ¡El factorial 16! = 20922789888000 y 20922789888000 en el sistema 16 - 130777758000. Vemos que en el sistema de números final el factorial del número original tiene tres ceros. Si descomponemos 16 en factores primos, obtenemos 2, 2, 2, 2. Aquí solo tenemos un número único, por lo tanto, el elemento 2 se ejecuta solo una vez:

$$

$${16 \ over 2} + {16 \ over 4} + {16 \ over 8} + {16 \ over 16} + {16 \ over 32} + ... = 8 + 4 + 2 + 1 + 0 + ... = 15.$$

Cuando nos descomponemos, teníamos cuatro deuces, por lo que dividimos la suma de las divisiones por 4 con redondeo a un entero menor: $$${15 \ sobre 4} = 3.$

PD: La mayor parte del material para el post traducido desde aquí . Publicado por Aditya Ramesh .