Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 04-03-2013 14:52:24

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Factorielle d'un Gogolpelx

Fait à la va-vite, corrigez les erreurs s'il y en a smile

Le nombre de zéros pour [latex]10^n[/latex] est déjà minoré :
[TeX]f(10^n) \ge 2^{n-2}(5^n-1)[/TeX]
Donc [latex]\frac{f(10^n)}{10^n} \ge \frac{1}{4} - \frac{1}{4 \times 5^n}[/latex]

et, en passant à la limite, [latex]\lim_{n \to \infty} \frac{f(10^n)}{10^n} \ge \frac{1}{4}[/latex]

Ensuite, comme le montre ma petite étude rapide, [latex]f(10^n) = 2^{n-2}(5^n-1) + \sum_{i=n + 1}^{\infty} E \left( \frac{10^n}{5^i} \right)[/latex]
[TeX]= 2^{n-2}(5^n-1) + \sum_{i=1}^{\infty} E \left( \frac{2^n}{5^i} \right)[/TeX]
[TeX]= 2^{n-2}(5^n-1) + f(2^n)[/TeX]
[TeX]\le 2^{n-2}(5^n-1) + 2^n[/TeX]
Du coup, [latex]\frac{f(10^n)}{10^n} \le \frac{1}{4} - \frac{1}{4 \times 5^n} + \frac{1}{5^n}[/latex] et on a encore une limite qui vaut un quart.

On conclut avec le théorème des gendarmes, et on trouve une approximation du nombre de zéros d'un gogolplex qui vaut un quart de gogolplex smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

#0 Pub

 #27 - 04-03-2013 17:07:25

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Factorielle d''un Gogolplex

Oui bravo Mathias, tout est bon. L'encadrement pourrait être un peu plus fin, mais il suffit à ce que tu voulais prouver.

Il reste à prouver que la limite de [latex]\frac{f(n)}n[/latex] est [latex]\frac14[/latex].

 #28 - 04-03-2013 19:12:07

herbert
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 8

Factorielle d'un Gogolple

je reprends mon message en corrigeant les erreurs et je donne également un encadrement de la valeur recherchée à un gogol près. Je vais essayer de pas chambouler la mise en page du forum.

herbert a écrit:

soit [latex]x[/latex] un nombre entier dont on veut calculer le nombre de zéros à la fin de sa factorielle [latex]x![/latex].
Ceci revient à calculer le nombre de [latex]5[/latex] dans la décomposition en facteurs premiers de [latex]x![/latex]
Le nombre de facteurs 5 dans [latex]x[/latex] est donné par:
[TeX]f(x)=\sum_{i=1}^{\infty }\left \lfloor \frac{x}{5^{i}} \right \rfloor[/latex]

Il nous faut calculer [latex]f(x)[/latex] pour [latex]x[/latex] sous la forme [latex]x=10^{n}[/latex].
[latex]f(10^n)=\sum_{i=1}^{\infty }\left \lfloor \frac{10^n}{5^i} \right \rfloor=2^{n}\sum_{i=1}^{n}\left \lfloor \frac{5^{n}}{5^{i}} \right \rfloor+ \sum_{i=n+1}^{\infty }\left \lfloor \frac{2^{n}5^{n}}{5^{i}} \right \rfloor[/TeX]
[TeX]  =2^{n}\frac{(5^{n}-1)}{4}+\sum_{j=1}^{n}\left \lfloor \frac{2^{n}}{5^{j}} \right \rfloor[/TeX]
On voit bien ici l'erreur commise, j'ai oublié de calculer le nombre de zéros derrière [latex]2^{n}![/latex].
Ensuite on peut dire que:
[TeX]\frac{2^{n}}{5^{j}} - 1< \left \lfloor \frac{2^{n}}{5^{j}} \right \rfloor\leqslant \frac{2^{n}}{5^{j}}[/TeX]
[TeX]\sum_{j=1}^{n}(\frac{2^{n}}{5^{j}} - 1)=(\sum_{j=1}^{n}\frac{2^{n}}{5^{j}})-n[/TeX]
[TeX]\sum_{j=1}^{n}\frac{2^{n}}{5^{j}}=2^{n}\frac{5^{n}-1}{4 \times 5^{n}}[/TeX]
et donc
[TeX]2^{n}\frac{(5^{n}-1)}{4}+2^{n}\frac{5^{n}-1}{4 \times 5^{n}}-1< f(10^n)\leqslant 2^{n}\frac{(5^{n}-1)}{4}+2^{n}\frac{5^{n}-1}{4 \times 5^{n}}[/TeX]
on réorganise
[TeX]2^{n}\frac{(5^{n}-1)}{4}+2^{n}\frac{5^{n}-1}{4 \times 5^{n}}=\frac{2^{n}(5^{2n}-1)}{4 \times 5^{n}}[/TeX]
au final on obtient un encadrement à n près:
[TeX]\frac{2^{n}(5^{2n}-1)}{4 \times 5^{n}}-n< f(10^n)\leqslant \frac{2^{n}(5^{2n}-1)}{4 \times 5^{n}}[/TeX]
qui est plus lisible en:
[TeX]\frac{10^{n}}{4}-n-\frac{2^{n-2}}{5^{n}}< f(10^n)\leqslant\frac{10^{n}}{4}-\frac{2^{n-2}}{5^{n}}[/TeX]
remarquons que
[TeX]\frac{2^{n-2}}{5^{n}}<1[/TeX]
et donc:
[TeX]\frac{10^{n}}{4}-(n+1)< f(10^n)\leqslant\frac{10^{n}}{4}[/TeX]
pour un gogol ça donne
[TeX]f(10^n)\leqslant 25000000000000000000000000000000000000000000000[/TeX]
[TeX]00000000000000000000000000000000000000000000000000000[/TeX]
[TeX]f(10^n)> 24999999999999999999999999999999999999999999999[/TeX]
[TeX]99999999999999999999999999999999999999999999999999899[/TeX]
pour un gogolplex le nombre de zéros se situe entre 1/4 de gogolplex et 1/4 de gogolplex moins un gogol+1.

 #29 - 04-03-2013 19:30:26

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

factorielle d'un gogolplzx

Je vois que rigogolez bien, ici...

lol
http://perlbal.hi-pi.com/blog-images/102606/mn/1129560026.gif


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #30 - 04-03-2013 19:36:47

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

factorielle d'un gogolplec

Oui, bravo herbert. Cela donne un encadrement très précis.

2 petites remarques :

En fait l'inégalité est stricte à droite : [latex]f(10^n)<\frac{10^n}4[/latex]

A gauche, on peut faire un petit peu mieux en constatant que la somme des [latex]E\left(\frac{2^n}{5^j}\right)[/latex] s'arrête bien avant [latex]j=n[/latex].

Sinon, pour le cas général, ce n'est pas très éloigné du cas [latex]10^n[/latex].

 #31 - 04-03-2013 21:14:09

herbert
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 8

Fctorielle d'un Gogolplex

Ça fait un bel encadrement facile à lire wink
Sinon pour le cas n=0 on est obligé de garder l'égalité.

 #32 - 05-03-2013 01:59:08

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Factoriell ed'un Gogolplex

L'inégalité stricte à droite est toujours valable, même pour le cas n=0.

En arrêtant la somme des [latex]E\left(\frac{2^n}{5^j}\right)[/latex] à [latex]j=E\left(\frac{\ln 2}{\ln 5}n\right)[/latex], on obtient :
[TeX]f(10^n) \geq \frac{10^n}4 - E\left(\frac{\ln 2}{\ln 5}n\right) - \frac{2^{n-2}}{5^{E\left(\frac{\ln 2}{\ln 5}n\right)}}[/TeX]
donc [latex]f(10^n) \geq \frac{10^n}4 - E\left(\frac{\ln 2}{\ln 5}n\right) - 1[/latex]

Avec [latex]\frac{\ln 2}{\ln 5}\simeq 0,43[/latex], on y gagne un petit peu en précision.

Ainsi, pour un gogol ça donne :
[TeX]f(10^{100}) \leq 24999999999999999999999999999999999999999999999[/TeX]
[TeX]99999999999999999999999999999999999999999999999999999[/TeX][TeX]f(10^{100}) \geq 24999999999999999999999999999999999999999999999[/TeX]
[TeX]99999999999999999999999999999999999999999999999999957[/TeX]

 #33 - 05-03-2013 08:53:05

SHTF47
Imprnnçbl de Prs2Tt
Enigmes résolues : 39
Messages : 1629
Lieu: Autre nom du colin

Factorielle d'uun Gogolplex

Moi les gogols jpeux pas les encadrer.

http://i-cms.lejdn.fr/image_cms/original/320262.jpg

Klim, attends moi...


La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]

 #34 - 05-03-2013 13:55:50

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

factorielle d'un hogolplex

Pour aller plus loin, je vous propose de passer en base 5 (notations avec une barre au-dessus des chiffres) pour comprendre ce qui se passe.

Nous allons y calculer [latex]g(2^9)=g(512)=g(\overline{4022})[/latex] :

Tout d'abord [latex]f(\overline{4022})=\overline{402}+\overline{40}+\overline{4}[/latex]

D'autre part, [latex] \overline{4022}/4 =\overline{402,2}+\overline{40,22}+\overline{4,022}+\overline{0,4022}+\overline{0,04022}+...[/latex]

donc [latex]g(\overline{4022})=\overline{0,2}+\overline{0,22}+\overline{0,022}+\overline{0,4022}+\overline{0,04022}+...[/latex]
[TeX]=\overline{0,22222...}+\overline{0,222222...}+\overline{0,444444...}=\frac{2+2+4}4=2[/TeX]
On voit que [latex]g(n)[/latex] est égal au quart de la somme des chiffres de [latex]n[/latex] en base 5.

On peut ainsi, par exemple, aisément calculer à la main le nombre de zéros de
1 000 000 000 000 000! en cherchant [latex]2^{15}[/latex] en base 5 :
2, 4, 13, 31, 112, 224, 1003, 2011, 4022, 13044, 31143, 112341, 230232, 1011014, 2022033.

Ainsi [latex]g(10^{15})=\frac{2+0+2+2+0+3+3}{4}=3[/latex]

et donc [latex]f(10^{15})=249 999 999 999 997[/latex]

Avec un peu de patience, on peut même calculer à la main le nombre de zéros de gogol!, en trouvant que
[TeX]2^{100} = \overline{10241422120332320213311333103110222010033001}[/TeX]
d'où [latex]g(2^{100})=72/4=18[/latex] et donc
[TeX]f(10^{100})=249999999999999999999999999999999999999999999[/latex][latex]9999999999999999999999999999999999999999999999999999982[/TeX]
Pour finir, ceci permet de donner un encadrement de [latex]f(n)[/latex], puisque le nombre de chiffres de [latex]n[/latex] dans son écriture en base 5 est donné par [latex]E(\log_5(n))+1[/latex] et donc
[TeX]\frac{n}4-E(\log_5(n))-1 \leq f(n) < \frac{n}4[/TeX]
Ceci montre que [latex]\frac{f(n)}{n}[/latex] tend vers [latex]\frac14[/latex].

 #35 - 08-03-2013 14:12:01

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Factoriellle d'un Gogolplex

MthS-MlndN a écrit:

PS : Herbert et Shadock, vous avez pourri la mise en page du forum avec vos formules à rallonge, merci d'utiliser la fonction de prévisualisation smile Herbert, c'est un Latex très simplifié qui est dispo, les sauts à la ligne fonctionnent mal et les inserts de texte dans les formules ne marchent pas très bien...

Euh moi ça ne pourri pas l'afichage que j'ai...


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #36 - 08-03-2013 22:40:14

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

facrorielle d'un gogolplex

shadock a écrit:

Euh moi ça ne pourri pas l'afichage que j'ai...

Bah maintenant non, vu que j'ai tout édité pour raccourcir les lignes.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #37 - 08-03-2013 23:01:04

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Factorielle d'un GGogolplex

Ah bah désolé smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete