Nombre de zéros de n factoriel ; n grand⚓︎

On rappelle que, pour \(n\) un entier naturel, la factorielle de \(n\) se note \(n!\) et se définit comme le produit des entiers de \(1\) à \(n\).

\(0! = 1\), comme un produit vide.
\(1! = 1\)
\(2! = 1×2 = 2\)
\(3! = 1×2×3 = 6\)
\(11! = 1×2×3×4×5×6×7×8×9×10×11 = 39916800\)
\(42! = 1405006117752879898543142606244511569936384000000000\)

On constate que

\(3!\) se termine par aucun zéro.
\(11!\) se termine par 2 zéros.
\(42!\) se termine par 9 zéros.

Construire une fonction, tel que nb_zeros_factorielle(n) renvoie le nombre de zéros dans l'écriture décimale de \(n!\), pour \(n\) entier inférieur à \(10^{18}\).

Exemples

🐍 Console Python

>>> nb_zeros_factorielle(3)
0
>>> nb_zeros_factorielle(11)
2
>>> nb_zeros_factorielle(42)
9

###

# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(3) == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(11) == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(42) == 9bksl-nlbksl-nl# autre testsbksl-nlbksl-nl"""bksl-nlfor n in range(100):bksl-nl print(nbpy-undzerospy-undfactorielle(n), end=", ")bksl-nlbksl-nlfrom random import py-strbksl-nlfor i in range(17):bksl-nl for py-und in range(10):bksl-nl n = randrange(10py-strpy-stri, 10py-strpy-str(i+1))bksl-nl print((n, nbpy-undzerospy-undfactorielle(n)), end=", ")bksl-nl"""bksl-nlbksl-nlPETITS = [bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 0,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 2,bksl-nl 2,bksl-nl 2,bksl-nl 2,bksl-nl 2,bksl-nl 3,bksl-nl 3,bksl-nl 3,bksl-nl 3,bksl-nl 3,bksl-nl 4,bksl-nl 4,bksl-nl 4,bksl-nl 4,bksl-nl 4,bksl-nl 6,bksl-nl 6,bksl-nl 6,bksl-nl 6,bksl-nl 6,bksl-nl 7,bksl-nl 7,bksl-nl 7,bksl-nl 7,bksl-nl 7,bksl-nl 8,bksl-nl 8,bksl-nl 8,bksl-nl 8,bksl-nl 8,bksl-nl 9,bksl-nl 9,bksl-nl 9,bksl-nl 9,bksl-nl 9,bksl-nl 10,bksl-nl 10,bksl-nl 10,bksl-nl 10,bksl-nl 10,bksl-nl 12,bksl-nl 12,bksl-nl 12,bksl-nl 12,bksl-nl 12,bksl-nl 13,bksl-nl 13,bksl-nl 13,bksl-nl 13,bksl-nl 13,bksl-nl 14,bksl-nl 14,bksl-nl 14,bksl-nl 14,bksl-nl 14,bksl-nl 15,bksl-nl 15,bksl-nl 15,bksl-nl 15,bksl-nl 15,bksl-nl 16,bksl-nl 16,bksl-nl 16,bksl-nl 16,bksl-nl 16,bksl-nl 18,bksl-nl 18,bksl-nl 18,bksl-nl 18,bksl-nl 18,bksl-nl 19,bksl-nl 19,bksl-nl 19,bksl-nl 19,bksl-nl 19,bksl-nl 20,bksl-nl 20,bksl-nl 20,bksl-nl 20,bksl-nl 20,bksl-nl 21,bksl-nl 21,bksl-nl 21,bksl-nl 21,bksl-nl 21,bksl-nl 22,bksl-nl 22,bksl-nl 22,bksl-nl 22,bksl-nl 22,bksl-nl]bksl-nlfor n, attendu in enumerate(PETITS):bksl-nl assert nbpy-undzerospy-undfactorielle(n) == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nlbksl-nlCOUPLES = [bksl-nl (7, 1),bksl-nl (2, 0),bksl-nl (9, 1),bksl-nl (9, 1),bksl-nl (2, 0),bksl-nl (4, 0),bksl-nl (6, 1),bksl-nl (3, 0),bksl-nl (5, 1),bksl-nl (8, 1),bksl-nl (16, 3),bksl-nl (97, 22),bksl-nl (78, 18),bksl-nl (98, 22),bksl-nl (58, 13),bksl-nl (45, 10),bksl-nl (93, 21),bksl-nl (68, 15),bksl-nl (41, 9),bksl-nl (68, 15),bksl-nl (685, 170),bksl-nl (659, 163),bksl-nl (530, 131),bksl-nl (493, 120),bksl-nl (683, 169),bksl-nl (845, 209),bksl-nl (770, 191),bksl-nl (982, 243),bksl-nl (365, 89),bksl-nl (289, 70),bksl-nl (1050, 261),bksl-nl (9455, 2362),bksl-nl (7537, 1882),bksl-nl (7536, 1882),bksl-nl (9362, 2336),bksl-nl (8394, 2095),bksl-nl (3254, 812),bksl-nl (6188, 1543),bksl-nl (7051, 1761),bksl-nl (7006, 1750),bksl-nl (22793, 5695),bksl-nl (91583, 22892),bksl-nl (28019, 7000),bksl-nl (25766, 6439),bksl-nl (66010, 16500),bksl-nl (85762, 21438),bksl-nl (98464, 24612),bksl-nl (27779, 6941),bksl-nl (92939, 23230),bksl-nl (17577, 4392),bksl-nl (664955, 166234),bksl-nl (392167, 98039),bksl-nl (219530, 54880),bksl-nl (596024, 149001),bksl-nl (852393, 213093),bksl-nl (757725, 189427),bksl-nl (537003, 134247),bksl-nl (569746, 142432),bksl-nl (720321, 180076),bksl-nl (760423, 190100),bksl-nl (9864166, 2466038),bksl-nl (3936351, 984084),bksl-nl (2554139, 638530),bksl-nl (5600487, 1400116),bksl-nl (6148810, 1537198),bksl-nl (4758791, 1189693),bksl-nl (8249433, 2062353),bksl-nl (3571734, 892927),bksl-nl (1840833, 460203),bksl-nl (6806599, 1701644),bksl-nl (58037629, 14509402),bksl-nl (27880791, 6970192),bksl-nl (31921612, 7980396),bksl-nl (41858181, 10464540),bksl-nl (71827981, 17956988),bksl-nl (42356047, 10589005),bksl-nl (39048190, 9762041),bksl-nl (45274424, 11318599),bksl-nl (39599801, 9899945),bksl-nl (97036229, 24259050),bksl-nl (800398176, 200099539),bksl-nl (140720239, 35180054),bksl-nl (278646632, 69661652),bksl-nl (597677495, 149419368),bksl-nl (981777051, 245444257),bksl-nl (975014653, 243753656),bksl-nl (432577103, 108144268),bksl-nl (530968050, 132742006),bksl-nl (879778198, 219944544),bksl-nl (628192898, 157048217),bksl-nl (1399829940, 349957478),bksl-nl (5074896726, 1268724173),bksl-nl (9860267700, 2465066919),bksl-nl (9692888733, 2423222173),bksl-nl (2704381881, 676095466),bksl-nl (5774520969, 1443630233),bksl-nl (2240891591, 560222891),bksl-nl (6811274839, 1702818701),bksl-nl (5961817060, 1490454259),bksl-nl (7826628749, 1956657180),bksl-nl (41136662363, 10284165581),bksl-nl (52565037117, 13141259271),bksl-nl (63607552056, 15901888008),bksl-nl (23188519592, 5797129889),bksl-nl (89748095845, 22437023954),bksl-nl (15650281184, 3912570286),bksl-nl (50090331406, 12522582847),bksl-nl (20967136984, 5241784238),bksl-nl (14344138004, 3586034492),bksl-nl (53772868694, 13443217164),bksl-nl (975871201654, 243967800405),bksl-nl (482703545289, 120675886314),bksl-nl (331273451253, 82818362807),bksl-nl (395076944881, 98769236211),bksl-nl (189815352140, 47453838029),bksl-nl (788906837428, 197226709349),bksl-nl (928843071399, 232210767841),bksl-nl (553488566695, 138372141666),bksl-nl (254134881665, 63533720409),bksl-nl (758622380618, 189655595143),bksl-nl (6488379282292, 1622094820565),bksl-nl (4356794834447, 1089198708602),bksl-nl (9656612303548, 2414153075878),bksl-nl (7644224478447, 1911056119603),bksl-nl (8610531572702, 2152632893167),bksl-nl (2009995664733, 502498916172),bksl-nl (7034946412203, 1758736603042),bksl-nl (8848382740005, 2212095684991),bksl-nl (4383738122351, 1095934530577),bksl-nl (2781408666826, 695352166698),bksl-nl (87286132334981, 21821533083732),bksl-nl (42589487541999, 10647371885489),bksl-nl (54696969378075, 13674242344508),bksl-nl (57765126008076, 14441281502008),bksl-nl (58176286397091, 14544071599265),bksl-nl (75050064429567, 18762516107381),bksl-nl (89192156333243, 22298039083301),bksl-nl (12989438872457, 3247359718104),bksl-nl (41916706897524, 10479176724370),bksl-nl (87531669966937, 21882917491724),bksl-nl (510580878072362, 127645219518079),bksl-nl (786049640068306, 196512410017067),bksl-nl (111801193096217, 27950298274043),bksl-nl (668069621008732, 167017405252172),bksl-nl (571615903728973, 142903975932230),bksl-nl (670800572001129, 167700143000272),bksl-nl (132999948308075, 33249987077007),bksl-nl (521818723804123, 130454680951017),bksl-nl (545190359796199, 136297589949035),bksl-nl (670360049737213, 167590012434292),bksl-nl (3495053667342183, 873763416835534),bksl-nl (3253069295544998, 813267323886235),bksl-nl (8404818041669655, 2101204510417403),bksl-nl (2862987795683907, 715746948920967),bksl-nl (7536249205455639, 1884062301363898),bksl-nl (6126641325199803, 1531660331299938),bksl-nl (5937109965109064, 1484277491277255),bksl-nl (5401717470040138, 1350429367510023),bksl-nl (5398925943459609, 1349731485864894),bksl-nl (5148530753646852, 1287132688411700),bksl-nl (67589630016912814, 16897407504228190),bksl-nl (79506573195211867, 19876643298802952),bksl-nl (43711590897574851, 10927897724393699),bksl-nl (35862471175212753, 8965617793803179),bksl-nl (99369028741191436, 24842257185297846),bksl-nl (77557972579435142, 19389493144858774),bksl-nl (55649795884135111, 13912448971033764),bksl-nl (59000293312803830, 14750073328200946),bksl-nl (14954805986036612, 3738701496509142),bksl-nl (31017683057609138, 7754420764402274),bksl-nl]bksl-nlfor n, attendu in COUPLES:bksl-nl assert nbpy-undzerospy-undfactorielle(n) == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl ∞/∞

def nbpy-undzerospy-undfactorielle(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(3) == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(11) == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle(42) == 9bksl-nlbksl-nldef nbpy-undzerospy-undfactorielle(n):bksl-nl resultat = 0bksl-nl puisspy-und5 = 5bksl-nl while puisspy-und5 <= n:bksl-nl resultat += n // puisspy-und5bksl-nl puisspy-und5 py-str= 5bksl-nl return resultatbksl-nlbksl-nl

A

Cette méthode se généralise pour déterminer la valuation \(p\)-adique d'un entier \(n\).

Si \(n\) est un entier naturel, et \(p\) un nombre premier, la formule de Legendre donne l'exposant de \(p\) dans la décomposition en facteur premier de \(n!\).

\[v_p(n!) = \sum_{k=1}^{\infty} \lfloor \frac{n}{p^k} \rfloor = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \cdots\]

La somme s'arrête ; tous les termes sont nuls à partir d'un certain rang.
\(\lfloor \frac{a}{b} \rfloor\) est la partie entière de \(a\) divisé par \(b\). Avec Python, on peut simplement faire a // b.

Cela donne une fonction Python

🐍 Script Python

def valuation(n, p):
    """Renvoie la valuation p-adique de n!
    - n est un entier naturel
    - p est un nombre premier
    """
    resultat = 0
    puiss_p = p
    while puiss_p <= n:
        resultat += n // puiss_p
        puiss_p *= p
    return resultat

On peut se servir de cette fonction pour obtenir la décomposition complète en facteurs premiers de \(n!\), mais aussi de coefficients binomiaux qui se calculent avec des factorielles.

Il faudra juste avoir une liste de nombres premiers... C'est toujours très utile.

Z

Indice 1

Il n'est pas possible de construire un tableau de tous les résultats.
Il faut penser décomposition en facteurs premiers de \(n!\).
Une divisibilité par \(10\) signifie la présence de \(2\) et \(5\) dans la décomposition.
Le nombre de zéros d'un nombre est le minimum de l'exposant de 2 et de celui de 5 dans la décomposition en facteurs premiers du nombre.
Pour \(n!\), le nombre de zéros est l'exposant de 5 qui est plus petit que l'exposant de 2.

Indice 2

Combien y a-t-il de multiples de 5 de \(1\) à \(n\) ? Chacun apporte un zéro.
Combien y a-t-il de multiples de 25 de \(1\) à \(n\) ? Chacun apporte un zéro supplémentaire.
Combien y a-t-il de multiples de 125 de \(1\) à \(n\) ? Chacun apporte un zéro supplémentaire.
Quand faut-il arrêter cette liste ? Et comment la générer ?

Indice 3

On utilisera une variable puiss_5 qui sera une puissance de 5.
La puissance suivante s'obtient avec puiss_5 *= 5.
Il y a n // k multiples de \(k\) de \(1\) à \(n\), par exemple :
- Il y a 42 // 5 = 8 multiples de 5 de \(1\) à \(42\) : \(5\), \(10\), \(15\), \(20\), \(25\), \(30\), \(35\) et \(40\).
- Il y a 42 // 25 = 1 multiple de 25 de \(1\) à \(42\) : \(25\).
- Il y a 42 // 125 = 0 multiple de 125 de \(1\) à \(42\).
Il y a \(8+1+0=9\) zéros à la fin de \(42!\)