Compter les zéros de fin des nombres factoriels dans n'importe quel système numérique

Comment puis-je calculer le nombre de zéros de fin de la factorielle d'un nombre dans un certain système numérique?

Examinons le cas lorsque nous sommes dans le système de 10e nombre, puis voyons comment nous pouvons généraliser cela en une solution universelle. On nous donne le nombre N et pour sa factorielle, nous devons trouver le nombre de zéros de fin. La solution sera assez simple - la somme:

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

Nous pouvons le généraliser dans une telle formule:

$$

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

Pourquoi 5? C'est simple. Le zéro final n'est obtenu que lorsque le nombre a 10 dans la factorielle. Ainsi, en comptant le nombre de dizaines dans la factorielle, on trouve le nombre de zéros finis.

Pourquoi dans l'exemple ci-dessus, nous divisons par 5? Parce que 10 peut être obtenu en multipliant 5 par 2. Par conséquent, la solution complète aura deux formules:

$$

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

et

$$

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

Mais, en raisonnant logiquement, nous savons que le premier montant sera inférieur, nous n'avons donc qu'à le calculer (plus de détails peuvent être trouvés ici ).

Solution à notre problème

Pour calculer les zéros finaux de la factorielle d'un nombre dans un système numérique spécifique, j'ai compilé l' algorithme ci-dessous:

1. Factorisez le nombre B du système numérique.
2. Divisez le nombre N par chaque facteur premier unique K, multipliant K par lui-même jusqu'à $$$N \ sur K$sera plus d'un, tout en arrondissant chaque résultat à un entier plus petit.
3. Si, en augmentant le nombre du système numérique, nous obtenons plusieurs facteurs premiers K identiques, alors nous devons diviser le résultat ci-dessus par le nombre de K identiques.
4. De toutes les divisions de N par chaque facteur K unique, choisissez le plus petit quotient, qui sera notre réponse.

Je vais le montrer avec un exemple.
Soit le nombre N = 5, le système numérique B = 12. Factoriel 5! = 120, et 120 dans le 12e système est A0. Nous voyons que dans un système de nombres finis, la factorielle du nombre d'origine a un zéro. Si nous décomposons 12 en facteurs premiers, nous obtenons 2, 2, 3. Nous avons deux nombres uniques: 2 et 3. Suite à notre algorithme, nous remplirons le point 2 avec le nombre 2.

$$

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

Mais le diable s'est rencontré deux fois dans la décomposition de 12, nous divisons donc le résultat final par 2 et arrondi à un entier plus petit. En conséquence, nous obtenons 1.

On fait de même avec 3:

$$

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

Ainsi, nous avons obtenu deux quotients de divisions du nombre N par des facteurs premiers du nombre du système numérique. Ils sont tous deux égaux à 1, nous n'avons donc pas à choisir le plus petit et nous donnons simplement la réponse - 1.

Prenons un autre exemple.

Soit le nombre N = 16, le système numérique B = 16. Le factoriel 16! = 20922789888000 et 20922789888000 dans le 16e système - 130777758000. Nous voyons que dans le système de numérotation final, la factorielle du nombre d'origine a trois zéros. Si nous décomposons 16 en facteurs premiers, nous obtenons 2, 2, 2, 2. Ici, nous n'avons qu'un seul numéro unique, par conséquent, l'élément 2 n'est exécuté qu'une seule fois:

$$

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

Lorsque nous avons décomposé, nous avions quatre égalités, nous divisons donc la somme des divisions par 4 en arrondissant à un entier plus petit: $$${15 \ over 4} = 3.$

PS La plupart des éléments de l'article ont été traduits d'ici . Publié par Aditya Ramesh .