Devoir de vacances

Dimanche 8 août 2010 7 08 /08 /Août /2010 11:34

Devoir de vacances

(inspiré du magazine Tangente, novembre 2009)

Par combien de 0 se termine le nombre 2010!?

(c'est à dire le nombre factorielle de 2010, soit 2010! = 2010×2009×2008...×2×1). On ramasse les copies à la rentrée.

Plus
- Email
- Lien
- Imprimer

Par Alexandre Moatti - Publié dans : "Jeux" et curiosités mathématiques - Communauté : Les amis des maths
Ecrire un commentaire - Voir les 10 commentaires

Précédent : Cercles d'un cône Retour à l'accueil Suivant : In memoriam

Commentaires

501. Consulter le lien vers "mon site" pour l'algorithme.

Commentaire n°1 posté par ecjs le 08/08/2010 à 12h40

Cher ecjs, bravo, c'est la bonne réponse, et merci d'avoir conçu cet algorithme. Mais attention, certains puristes voudront une démonstration mathématique et non un algorithme! (dans le théorème des 4 couleurs, certains mathématiciens refusent la partie de démonstration algorithmique et attendent encore la démonstration a mano complète ! ) A.M.

Réponse de Alexandre Moatti le 08/08/2010 à 14h12

Thomas (sur Facebook - eh oui on se disperse, çà ne va pas du tout) a apporté un commentaire intéressant : "~25% de la valeur de N pour N grand ? A démontrer aussi ...", auquel j'ai répondu : Flûte ! C'est tellement simple ces petits problèmes avec un cas particulier (2010), çà évite de chercher la solution générique ! Mais merci Thomas de m'y avoir forcé, et bravo c'est bien çà (N/4 pour N grand) - çà se démontre facilement une fois qu'on a la formule générique (qui est très surprenante à dire vrai - si je ne me suis pas trompé)... A.M.

Commentaire n°2 posté par AM le 09/08/2010 à 10h50

Rapidement:

Hm... le nombre de zéros est déterminé par le nombre de "facteurs 10"; c'est-à-dire, puisqu'il y a beaucoup plus de facteurs 2 que de facteurs 5, ce nombre de zéros est déterminé par la puissance du facteur 5 lors de la décomposition en produit de facteurs premiers de (2010!). Appelons-le Z.

Examinons les puissances de 5, inférieures à 2010:

5^2=25

5^3=125

5^4=625

5^5=3125 > 2010 ; trop grand.

Pour N<25, on montre par récurrence que Z(N!)=Floor(N/5) [Floor=partie entière]

Pour 25<N<125, il faut y ajouter les multiples de 25 (comptés une fois, parmi les multiples de 5) et donc: Z(N!)=Floor(N/5)+Floor(N/5²)

... etc

Pour N=2010, la formule est donc:

Z(N!)=Floor(N/5)+Floor(N/5²)+Floor(N/125)+Floor(N/625)

Z(2010!)=402+80+16+3

Z(2010!)=501

Une formule générale serait ainsi: Z(N!)=Sum[i=1 to i=Floor(ln(N)/ln(5))] { Floor(N/(5^i)) } Par contre, je vois mal comment montrer qu'elle tend vers N/4, si c'est bien le cas...

Commentaire n°3 posté par Orteil le 10/08/2010 à 13h23

La solution se google facilement, mais j'avoue que je ne suis pas complètement sûr de bien comprendre l'astuce, les gens n'expliquent pas super bien le raisonnement. Si je comprends bien, l'idée est de regarder le nombre de nombres divisibles par 5,25, 625, etc... et d'ajouter un zero pour chacun de ces nombres (puisque pour un facteur 5, on a forcément un facteur 2 auparavant). Effectivement, un raisonnement par récurrence me paraît plus safe !

Pour la convergence, vers N/4 c'est simple :

1/5+1/25+1/625+ ...=sum 1/5^n=1/4

Sinon, je me demande si le problème en lui-même est "facilité" par le fait que 10 se décompose en seulement 2 facteurs premier. Par exemple, une question qui me semble intéressante serait de savoir par combien de zeros se termine le même nombre en base 12. (est-ce que faire le même raisonnement sur 3 suffit ? pas sûr vu qu'il faut deux facteurs 2 pour un facteur 3 pour avoir 12).

Commentaire n°4 posté par Tom Roud le 10/08/2010 à 16h47

Tom Roud, le raisonnement direct (pas par récurrence) ma paraît correct et safe (et élégant je pense). On va chercher tous les multiples de 5 dans 2010!, on écrit donc 2010! = 5^^402 * 402! * des nombres non multiples de 5 ; on continue 402! = 5^^80*80!* des nombres non multiples de 5; idem 80! = 5^^16*16!*... ; 16!= 5^^3*3!*...; et stop 3! n'a plus de multiples de 5.

Au total 2010! = 5^^(402+80+16+3)* d'autres nombres non multiples de 5

Puis en effet on va chercher 501 nombres pairs dans 2010! (il y en a 1005 donc suffisamment) donc 2010 = (5*2)^^501* des nombres non multiples de 5 - donc exactement 501 fos le chifres 0 à la fin.

La formule générique que j'ai trouvée est E(N/5) + E(N/25) + E(N/125) +.... Pour N grand cette somme converge vers N/4 (en assimilant E(N/5) à N/5 mais passage à la limite pas évident à mon goût).

A.M.

Réponse de Alexandre Moatti le 12/08/2010 à 00h13

Je me réponds à moi-même pour le problème en base 12 (en base quelconque en fait) : il suffit de trouver le nombre de zéros en base 4 et le nombre de zéros en base 3 (ce qui est je pense relativement facile puisqu'il suffit de compter le nombre de facteurs divisible par 2 et 3 suivant un raisonnement similaire au cas du 5) et de prendre le minimum des deux. On peut aussi prendre les limites pour voir un effet potentiellement rigolo : le nombre de zeros à la fin de N! en base 2 tend vers N suivant la même sommation précédente, donc sauf erreur de ma part je pense que le nombre de zeros en base 4 tend vers N/2, de la même façon le nombre de zeros en base 3 tend a priori vers N*1/3+1/9+...=N/2, c'est le même nombre !

Commentaire n°5 posté par Tom Roud le 10/08/2010 à 17h20

Ah, bien vu, Tom Roud: il suffirait d'arrondir et de passer par une simple somme de puissances...

Z(N!)=Sum[i=1 to i=Floor(ln(N)/ln(5))] { Floor(N/(5^i)) }

Appelons n=Floor[ln(N)/ln(5)] - et Sn(k), la somme des n-ièmes puissances de k:

Sum [i=1 to i=n] {N/(5^i)} = N * [Sn(1/5) - 1]

Et comme notre valeur utilise des parties entières, on a l'inégalité suivante :

{N * [Sn(1/5) - 1] - n} <= Z(N!) <= {N * [Sn(1/5) - 1]}

Soit : {N * [Sn(1/5) - 1] - (N^(1/5)) - 1} < Z(N!) <= {N * [Sn(1/5) - 1]}

On utilise la formule:

Sn(k)=1+k+k²+...+k^n=[1-k^(n+1)]/(1-k)

Soit, ici: Sn(1/5) - 1 = [1 - (1/5)^(n+1)] / [(1-(1/5)] - 1

(1/5)^(n+1) tend vers 0 quand n tend vers l'infini; d'où, Sn(1/5)-1 tend vers: 1/(4/5)-1 = 1/4

L'inégalité devient :

{N /4 - (N^(1/5)) - 1} < Z(N!) <= (N /4) avec, certes: (N^0.2) << (N/4) , mais enfin, les deux termes divergent et donc, on n'a pas montré (encore) la convergence - sauf à ne considérer que la suite des nombres N puissances de 5 : (Uk) avec Uk =Z [(5^k)!] qui serait donc égal à Sn(1/5)-1, et tend bien vers N/4...

(J'espère que ce n'est pas trop illisible - ni trop incohérent, à raisonner en direct, "à haute voix")

Commentaire n°6 posté par Orteil le 10/08/2010 à 18h43

On n'a pas convergence (ce n'est pas une limite) mais équivalence, non ?

Clairement, on a |(Sum(Floor(N/5^j))-Sum(N/5^j)|<k avec k logarithmique en N (k est par exemple le nombre de termes dans la somme, toutes les différences entre parties entières et nombre sont majorées par 1), on divise par N et on prend la limite (lnN/N->0 à droite) ce qui montre que Sum(Floor(N/5^j))/N tend vers 1/4, d'où Sum(Floor(N/5^j)) équivalent à N/4.

Commentaire n°7 posté par Tom Roud le 11/08/2010 à 03h35

51!

Commentaire n°8 posté par Sabssia le 11/08/2010 à 23h50

402

Commentaire n°9 posté par Dr. Goulu le 21/09/2010 à 18h54

Ce problème peut se résoudre en utilisant la formule d'Adrien Marie Legendre que vous pouvez trouver là:

http://fr.wikipedia.org/wiki/Factorielle

La plus grand puissance d'un nombre premier p qui divise n! est donnée par:

somme de k=1 à l'infini de la partie entière de n/p^k (n divisé par p puissance k)

Cette somme a un nombre fini de termes qui sont non nuls.

Pour résoudre le problème donné il faut appliquer cette formule avec p=2 et p=5

et prendre le plus petit des deux nombres obtenus, c'est la plus grande puissance de 10 qui divise notre factorielle.

Commentaire n°10 posté par Fin de partie le 27/08/2011 à 19h55

1,2,3,4,5

Pourquoi ce blog ?

Indispensables astronomiques

Communauté de blogs

Recommander