Aller au contenu

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

A

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!\)
Retour en haut de la page