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
[+]

 #1 - 28-02-2013 00:58:26

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

Factorrielle d'un Gogolplex

Coucou !

Tiens, je me demandais l'autre soir combien il y avait de zéros à la fin de la factorielle d'un Gogolplex.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 28-02-2013 11:01:04

ksavier
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 166

Factorielle d'un Gogolpllex

Il y en a au moins [latex]10^{100}[/latex].
Mieux, il y en a au moins [latex]5\times10^{99}\times(10^{100}+1)[/latex].
Mieux, il y en a au moins [latex]10^{100}\left(1+45\times10^{99}\right)[/latex]

 #3 - 28-02-2013 12:39:17

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

Factorielle d'un Goolplex

[latex]n_0=\sum_{i=1}^{n}E\left(\frac{N}{5^i}\right)[/latex] avec [latex]n[/latex] le plus grand entier tel que [latex]E\left(\frac{N}{5^i}\right)=0[/latex] et [latex]E(x)[/latex] la partie entière de x.

Maintenant j'ai plus qu'à faire le calcul lol


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

 #4 - 28-02-2013 13:25:13

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

Factorielle d'un Gogoolplex

@ksavier : Tu es gogolplexement loin du résultat.

@shadock : Oui, c'est la bonne formule. Comme tu dis, y a plus qu'à calculer...
Pour un Gogol, c'est assez facile d'avoir la valeur exacte par ordinateur, mais pour un Gogolplex ?
Je me contenterais d'une bonne valeur approchée, ou mieux, d'un bon encadrement.

 #5 - 28-02-2013 13:51:56

ksavier
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 166

facyorielle d'un gogolplex

oui, je sais bien que je suis loin. Une minoration vaut mieux que rien du tout non ?big_smile

Et puis, il me faut connaître le nombre de multiple de 5 dans [latex]2^\text{gogol}[/latex]...Et là je bloque.

 #6 - 28-02-2013 14:25:13

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

Factorielle d'un GGogolplex

Tu comptes les "5", les "25", les "125", etc..., des facteurs.
Il y en a N(1/5+1/5²+1/5³+....)=N/5(1+x+x²+...)= N/4-epsilon
J'ai posé (x=1/5)

Vérification
Le test de 400! avec Wolfram Alpha donne 99 zéros sauf erreur.

Ça fait donc 1/4 de Gogolplex à très peu près, peut-être 1 de moins.

 #7 - 28-02-2013 15:20:16

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

Factoriielle d'un Gogolplex

Oui halloduda, bravo ! C'est une bonne valeur approchée. Après ce ne sera pas 1 de moins, mais plus que 1 de moins. Essaye de calculer pour factorielle un Gogol, tu verras.

 #8 - 28-02-2013 17:50:49

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

factorielle d'un gogolplec

De manière générale, dans [latex]X![/latex], il y a toujours plus de fois le facteur 2 que le facteur 5. On peut donc "seulement" compter le nombre de facteurs 5 qui apparaissent pour connaitre le nombre de zéros.

En notant [latex]E(\cdot)[/latex] la partie entière d'un nombre, on peut écrire que le facteur 5 apparait une fois dans [latex]E \left(\frac{X}{5} \right)[/latex] nombres entre 1 et X, deux fois dans [latex]E \left(\frac{X}{25} \right)[/latex] nombres, etc. On veut donc calculer
[TeX]\sum_{i=1}^{\infty} E \left(\frac{X}{5^i} \right)[/TeX]
et, dans notre cas, [latex]X = 10^{10^{100}}[/latex].
[TeX]\frac{X}{5} = 2 \times 10^{10^{100}-1}[/TeX]
[TeX]\frac{X}{25} = 4 \times 10^{10^{100}-2}[/TeX]
etc. donc
[TeX]\frac{X}{5^i} = 2^i \times 10^{10^{100}-i}[/TeX]
On peut aller jusqu'à
[TeX]\frac{X}{5^{10^{100}}} = 2^{10^{100}}[/TeX]
pour rester dans des valeurs entières. La division par 5 à partir de là s'avère plus problématique...

Ca nous donne déjà une somme partielle :
[TeX]\sum_{i=1}^{10^{100}} E \left(\frac{X}{5^i} \right) = 10^{10^{100}} \sum_{i=1}^{10^{100}} \frac{1}{5^i} [/TeX]
On peut calculer ça en faisant
[TeX]10^{10^{100}} \times \frac{1}{5} \times \frac{1 - \frac{1}{5^{10^{100}}}}{1 - \frac{1}{5}}[/TeX]
soit
[TeX]2^{10^{100}-2} \times \left( 5^{10^{100}}-1 \right)[/TeX]
Le nombre de zéros à rajouter ne doit pas être énorme, mais je ne vois pas vraiment comment l'obtenir pour l'instant.


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

 #9 - 28-02-2013 18:49:04

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

factoruelle d'un gogolplex

Pour [latex]10^{100}[/latex] j'ai [latex]n_0=24999999999999999999999999999999999999999999999999999[/latex]
[latex]99999999999999999999999999999999999999999999982[/latex] lol

A peu prêt un quart de gogol donc comme approximation je prendrai 1/4*10^10^100 pour le gogolplex smile


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

 #10 - 28-02-2013 21:18:58

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

factoriemle d'un gogolplex

@Mathias : Oui, tout cela est correct. J'ai réussi à calculer le nombre exact de zéros pour factorielle gogol, mais pas encore pour factorielle gogolplex : je ne sais pas si c'est possible. On peut déjà essayer d'en donner une bonne approximation.

Bravo à shadock qui a trouvé le nombre exact de zéros de factorielle gogol.

 #11 - 28-02-2013 22:03:13

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

factoroelle d'un gogolplex

10! a 2 zéros
Est-ce que:

100! --> 21 zéros (2x10+1)
1000! --> 211 zéros (21x10+1)
10000! --> 2111 zéros

Etc ?

 #12 - 28-02-2013 22:28:33

ksavier
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 166

Factorelle d'un Gogolplex

Dans le nombre M! le nombre de 0 est obtenu en obtenant l'exposant de 5 dans sa décomposition en nombre premier.

Pour obtenir ce nombre, il suffit de savoir combien de fois on peut diviser par 5 l'ensemble des nombres inférieurs  au nombre M.

Ici [latex]M=10^n[/latex] (avec n>2 et largement même !!)

Avec l'aide d'une suite géométrique de raison 5, on peut démontrer que le nombre de 0 dans M! est égal à la somme de  [latex]2^{n-2}\times(5^n-1)[/latex] et du nombre de 0 dans [latex]2^n![/latex].
Et là je bloque un peu ...

 #13 - 01-03-2013 09:37:23

ksavier
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 166

Factoirelle d'un Gogolplex

Pour n au moins égal à 2, on trouve dans le nombre [latex]M=10^n![/latex] exactement  [latex]2^{n-2}5^n-1[/latex] zéros.

Donc pour [latex]n=10^{100}[/latex], on obtient le nombre de zéros dans la factorielle de gogolplex. A savoir [latex]2^{10^{100}-2}\times5^{10^{100}}-1[/latex] zéros.

 #14 - 01-03-2013 11:51:04

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

factorielle d'yn gogolplex

Nombrilist a écrit:

10! a 2 zéros
Est-ce que:

100! --> 21 zéros (2x10+1)
1000! --> 211 zéros (21x10+1)
10000! --> 2111 zéros

Non, par exemple 100! a 24 zéros.
Essaye de calculer pour 1000! et 10000! ce que ça donne.

ksavier a écrit:

le nombre de 0 dans (10^n)! est égal à la somme de  [latex]2^{n-2}\times(5^n-1)[/latex] et du nombre de 0 dans [latex]2^n![/latex]

Oui.

ksavier a écrit:

Pour n au moins égal à 2, on trouve dans le nombre [latex]M=10^n![/latex] exactement  [latex]2^{n-2}5^n-1[/latex] zéros.

Malheureusement pas. Le nombre de zéros de [latex]2^n![/latex] n'est pas [latex]2^{n-2}-1[/latex]. Des fois c'est moins. Par exemple pour [latex]n=6[/latex], le nombre de zéros de [latex]64![/latex] est [latex]12+2=14[/latex] et non [latex]15[/latex].

 #15 - 01-03-2013 15:12:18

ksavier
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 166

Factorielle d'un Gogolpllex

big_smile oui c'est très juste...

Je tourne en rond avec ce [latex]2^n[/latex]. Je n'arrive pas à l'exploiter correctement... Je crois que j'aurais besoin d'un indice...

 #16 - 02-03-2013 11:25:43

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

Factorielle d'un Gogollplex

Je n'ai pas d'indice à donner pour factorielle gogolplex vu que j'y suis pas arrivé moi-même ! big_smile

Voici cependant deux challenges qui me semblent intéressants à relever :

Calculer le nombre de zéros dans

1) 1 000 000 000!  de tête et sans aucun calcul compliqué.

2) gogol!

 #17 - 02-03-2013 12:01:02

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1945
Lieu: Paris

factorielle d'un gogomplex

Pour 1 000 000 !, avec mes connaissances ,
On devrait avoir déjà 21 (1+2+3+4+5+6) zéros avec :
10*100*1 000*10 000*100 000*1 000 000=1 000 000 000 000 000 000 000.

Puis 36 (1+3+5+7+9+11, c'est à dire (2*0+1)+(2*1+1)+...+(2*5+1)) autres zéros avec :
2*5*20*50*200*500*2 000*5 000*20 000*50 000*200 000*500 000
= 10*1 000*100 000*10 000 000*1 000 000 000*100 000 000 000
= 1 000 000 000 000 000 000 000 000 000 000 000 000.

De plus, on peut en avoir encore 30 (2+4+6+8+1) avec :
4*25*40*250*400*2 500*4 000*25 000*40 000*250 000
=100*10 000*1 000 000*100 000 000*10 000 000 000
=1 000 000 000 000 000 000 000 000 000 000.

Et 24 (3+5+7+9) autres avec :
8*125*80*1 250*800*12 500*8 000*125 000
=1 000*100 000*10 000 000*1 000 000 000
=1 000 000 000 000 000 000 000 000.

Et après, 28 (4+6+8+10) zéros avec :
16*625*160*6 250*1 600*62 500*16 000*625 000
=10 000*1 000 000*100 000 000*10 000 000 000
=10 000 000 000 000 000 000 000 000 000.

On continue, 21 (5+7+9) zéros avec :
32*3 125*320*31 250*3 200*312 500
=100 000*10 000 000*1 000 000 000
=1 000 000 000 000 000 000 000.

Encore 14 (6+8) zéros avec :
64*15 62*+640*156 250
=1 000 000* 100 000 000
=100 000 000 000 000.

Et enfin 16 (7+9) autres zéros avec :
128*78 125*1 280*781 250
=10 000 000*1 000 000 000
=10 000 000 000 000 000

J'ai oublié les 8 zéros avec :
256*390 625
=100 000 000
et les 9 zéros avec :
512*1953125
=1 000 000 000.

Ce qui fait un total d'au moins 207 (21+36+30+24+28+21+14+16+8+9) zéros pour 1 000 000 ! !!!

C'est énorme et je pense pas avoir oublié des zéros.
Pour expliquer ce que j'ai fait, j'ai d'abord pris le produit des puissances de 10 et puis le produit des puissances successives de 2 et de 5 car leur produit donne des zéros. On est obligé de s'arrêter à la puissance 9 car 5^10 est supérieur à 1 000 000.

Voilà et j'espère que c'est pas trop long.
_____________________________________________________________________
Et pour gogol !, comme il y'a 100 zéros, ça devrait être très long, déjà qu'on 207 zéros pour seulement 6 zéros. Trouver la puissance à laquelle, 5 dépasse gogol aiderait à avancer les choses, et on pourrait faire un algorithme ou un truc dans le genre ...

 #18 - 02-03-2013 14:11:35

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

factorielle d'un gogolplec

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]. On considère en effet que le nombre de [latex]2[/latex] est plus grand ou égal à [latex]5[/latex].
Si on prend [latex]\left \lfloor \frac{x}{5} \right \rfloor[/latex] on compte une fois tous les facteurs 5 pour chaque multiple de 5 à partir de [latex]x[/latex] jusque [latex]1[/latex]. Mais il faut aussi compter le 5 des multiples de 25 soit [latex]\left \lfloor \frac{x}{25} \right \rfloor[/latex], puis ceux de 125 et ainsi de suite.
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[/TeX]
Cette somme converge car le terme tend vers 0, et la suite est bornée par [latex]\left \lceil \frac{x}{5} \right \rceil\left \lfloor \frac{x}{5} \right \rfloor[/latex].

Il nous faut calculer [latex]f(x)[/latex] pour [latex]x[/latex] sous la forme [latex]x=10^{n}[/latex].
[TeX]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=2^n\sum_{j=0}^{n-1}5^{j}[/TeX]
On va calculer [latex]S=\sum_{j=0}^{n-1}5^{j}[/latex] comme suit:
[TeX]2S = (2\sum_{j=0}^{n-1}5^{j})+5^n-5^n[/TeX]
[TeX]= 5^0+5^0+5^1+5^1+5^2+5^2+5^3+ \cdots +5^{n-1}+5^n-5^n[/TeX]
On regroupe...
[TeX]=5^0+(5^0+5^1)+(5^1+5^2)+(5^2+5^3)+\cdots +(5^{n-1}+5^n)-5^n[/TeX]
[TeX]=5^0+5^0(1+5)+5^1(1+5)+5^2(1+5)+ \cdots +5^{n-1}(1+5)-5^n[/TeX]
[TeX]=(1-5^n)+6(5^0+5^1+5^2+ \cdots +5^{n-1})[/TeX]
[TeX]=(1-5^n)+6S
[/TeX]
soit
[TeX]
S=\frac{5^n-1}{4}
[/TeX]
Et donc:
[TeX]f(10^n)=2^n\frac{(5^n-1)}{4}=2^{n-2}(5^n-1)[/TeX]
on remplace [latex]n[/latex] par [latex]10^{100}[/latex] pour la réponse.

 #19 - 02-03-2013 14:29:11

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

Factorielle d'un Gogollplex

SabanSuresh a écrit:

Ce qui fait un total d'au moins 207 zéros pour 1 000 000 !

Tu es très loin du compte.


@Herbert : Tu oublies les zéros de [latex]2^n![/latex]

 #20 - 02-03-2013 14:51:19

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1945
Lieu: Paris

factorielle d'un gogolpkex

Ah bon, il me semble avoir tout fait, mais faut-il aussi calculer les zéros à l'intérieur du nombre ? Par exemple pour 12!=479 001 600, doit-on compter comme s'il y avait 4 zéros ou seulement 2 ?

 #21 - 02-03-2013 15:13:23

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

Factorielle dun Gogolplex

On ne compte que les zéros à la fin.

Essaye d'abord avec 10!, 100! puis 1000! avant d'attaquer 1 000 000 000!

 #22 - 02-03-2013 18:56:42

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

factorielle d'un gogolpkex

Oui c'est vrai j'ai fait des simplifications interdites, du coup c'est vachement plus dur. Je peux donner la réponse à 1 gogol près wink, par contre pour la réponse exacte je sais pas si j'ai les connaissances nécessaires.

 #23 - 03-03-2013 00:02:12

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

Factorielle d'un Gogolpleex

Ok j'ai compris comment on trouve 24 zéros dans 100 ! J'en trouve 24 grâce à 4*50, 4*25 et 4*75.

 #24 - 03-03-2013 10:18:08

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

factorielle d'un goholplex

herbert a écrit:

Oui c'est vrai j'ai fait des simplifications interdites, du coup c'est vachement plus dur.

On a visiblement fait le même calcul tous les deux, sauf que tu as oublié qu'il restait des parties entières non nulles pour i plus grand que n. On a le même résultat, et il est strictement inférieur à la réponse définitive.

Titou, peux-tu compiler nos réponses et donner le plus petit encadrement de la valeur attendue ?


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...


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

 #25 - 03-03-2013 23:57:36

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

faxtorielle d'un gogolplex

Voici un petit résumé de ce qui a pu être dit + quelques prolongements :

Notons [latex]f(n)[/latex] le nombre de zéros à la fin de [latex]n![/latex].
[TeX]f(n)[/latex] est le nombre de 5 dans la décomposition en produit de facteurs premiers de [latex]n![/latex].

[latex]f(n)=\sum_{i=1}^{\infty} E \left(\frac{n}{5^i} \right)[/TeX]
Par exemple, [latex]f(1 000)=200+40+8+1=249[/latex].

Dans la somme, chaque terme est le quotient du précédent par 5.
[TeX]f(5^n)=5^{n-1}+...+5+1=\frac{5^n-1}4[/TeX][TeX]f(10^n)=2^n f(5^n)+f(2^n)=\frac{10^n}4 + f(2^n) - \frac{2^n}4[/TeX]
Si l'on pose [latex]g(n)=\frac{n}4-f(n)[/latex], alors [latex]g(10^n)=g(2^n)[/latex].

Ceci permet de calculer aisément de tête [latex]f(10^9)[/latex] par exemple.
[TeX]g(10^9)=g(2^9)=g(512)=128-(102+20+4)=128-126=2[/TeX]
donc [latex]f(10^9)=249 999 998[/latex].

Voilà pour le résumé.

Pour ceux qui veulent aller plus loin, vous pouvez essayer de trouver un bon encadrement de [latex]f(n)[/latex], ce qui permettra de prouver que [latex]\frac{f(n)}{n}[/latex] tend vers [latex]\frac14[/latex]. Ce n'est pas hyper compliqué et je pourrai aider les courageux qui se lancent dans l'aventure.

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Sujets similaires

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