Contando zeros à direita de números fatoriais em qualquer sistema numérico

Como posso calcular o número de zeros à direita do fatorial de um número em um determinado sistema numérico?

Vejamos o caso quando estamos no sistema de números 10 e, em seguida, veja como podemos generalizar isso em uma solução universal. Recebemos o número N e, para seu fatorial, precisamos encontrar o número de zeros à direita. A solução será bastante simples - a soma:

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

Podemos generalizá-lo em uma fórmula:

$$

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

Por que 5? É simples O zero final é obtido apenas quando o número possui 10. No fatorial, portanto, contando o número de dezenas no fatorial, descobrimos o número de zeros finitos.

Por que no exemplo acima dividimos por 5? Como 10 pode ser obtido pela multiplicação de 5 por 2. Portanto, a solução completa terá duas fórmulas:

$$

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

e

$$

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

Mas, raciocinando logicamente, sabemos que o primeiro valor será menor, portanto, precisamos apenas calculá-lo (mais detalhes podem ser encontrados aqui ).

Solução para o nosso problema

Para calcular os zeros finais do fatorial de um número em um sistema numérico específico, compilei o algoritmo abaixo:

1. Fatore o número B do sistema numérico.
2. Divida o número N por cada fator primo único K, multiplicando K por si próprio até $$$N \ mais K$ será mais de um, arredondando cada resultado para um número inteiro menor.
3. Se, ao expandir o número do sistema numérico, obtivermos vários fatores primos K idênticos, devemos dividir o resultado acima pelo número de K. idênticos
4. De todas as divisões de N por cada fator único K, escolha o quociente menor, que será a nossa resposta.

Vou mostrar com um exemplo.
Seja o número N = 5, o sistema numérico B = 12. Fator 5! = 120 e 120 no 12º sistema é A0. Vemos que em um sistema de números finitos o fatorial do número original tem um zero. Se decompormos 12 em fatores primos, obteremos 2, 2, 3. Temos dois números únicos: 2 e 3. Seguindo nosso algoritmo, preencheremos o ponto 2 com o número 2.

$$

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

Mas o empate se encontrou duas vezes na decomposição de 12, então dividimos o resultado final por 2 e arredondamos para um número inteiro menor. Como resultado, obtemos 1.

Fazemos o mesmo com 3:

$$

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

Assim, obtivemos dois quocientes de divisões do número N por fatores primos do número do sistema numérico. Ambos são iguais a 1, então não precisamos escolher o menor e apenas damos a resposta - 1.

Considere outro exemplo.

Seja o número N = 16, o sistema numérico B = 16. O fatorial 16! = 20922789888000 e 20922789888000 no 16º sistema - 130777758000. Vemos que no sistema final de números o fatorial do número original possui três zeros. Se decompormos 16 em fatores primos, obteremos 2, 2, 2, 2. Aqui temos apenas um número único; portanto, o item 2 é executado apenas uma vez:

$$

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

Quando decompusemos, tínhamos quatro duques, portanto dividimos a soma das divisões por 4 com arredondamento para um número inteiro menor: $$${15 \ over 4} = 3.$

PS A maior parte do material para o post foi traduzido daqui . Postado por Aditya Ramesh .