Calculez les derniers chiffres du numéro de Graham

13

Le nombre de Graham se termine par un 7. C'est un nombre énorme, nécessitant en théorie plus d'informations à stocker que la taille de l'univers lui-même. Cependant, il est possible de calculer les derniers chiffres du nombre de Graham.

Les derniers chiffres sont:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Votre programme peut ne pas contenir ces chiffres (ou des chiffres similaires), mais doit les calculer. Il doit calculer 200 chiffres ou plus.

Sortie vers sortie standard. Temps d'exécution d'un maximum de 2 minutes sur un matériel décent. Le programme le plus court gagne.

code-golf number Thomas O
la source
Combien de chiffres doivent être imprimés?
Wile E. Coyote, le
@Dogbert D'oh. J'ai manqué ça. 200 ou plus serait bien.
Thomas O
Ruby ne calculera même pas 3**7625597484987alors que Python le fait :)
gnibbler
@gnibbler, euh comment? le résultat aurait plus de 3 billions de chiffres.
Wile E. Coyote, le
1
@Dogbert, avec suffisamment de mémoire et de temps, Python ira de l'avant et le calculera en utilisant ses longs. Ruby ne fera même pas 3 ** 5000000. semble avoir une sorte de limite
gnibbler

Réponses:

9

dc - 21 caractères

[3z202>xO200^|]dsxxrp

Cela prend environ une minute sur mon ordinateur et prendrait beaucoup plus de temps pour des valeurs supérieures à 200. Il ne produit pas de zéros non significatifs.

Voici une version légèrement plus longue mais plus rapide (26 caractères):

[3rAz^|dz205>x]dsxxAz6-^%p
3[3rAz^|dz202>x]dsxxAz3-^%p # or an extra character for a few less iterations
Nabb
la source
4

Haskell, 99

Des performances pas exceptionnelles, mais il parvient à calculer 500 chiffres en une minute sur mon matériel vieux de dix ans.

f a b|b==0=1|odd b=mod(a*f a(b-1))m|0<1=f(mod(a^2)m)$div b 2
main=print$iterate(f 3)3!!500
m=10^500

(btw, j'aimerais entendre parler de ses performances sur du matériel plus moderne)

JB
la source
Prend environ 19 secondes pour fonctionner sur mon PC. Sur une note latérale, cela n'imprime pas un 0 de tête avant la sortie.
Wile E. Coyote, le
Oui, c'est buggé sur tous les chiffres avec des zéros en tête. Calculez simplement 501 ;-) Merci pour la référence. L'avez-vous exécuté interprété ou compilé?
JB
Je l'ai compilé avec ghc -o g.exe g.hs. Je ne sais pas si c'est la meilleure façon de compiler.
Wile E. Coyote, le
Je viens de ghc -O3 graham.hs lancer Les options recommandées de badass du document en ligne semblent l'être -O2 -fvia-C. (et il semble que mon GHC a déjà quelques sorties de retard)
JB
Il semble fonctionner à la même vitesse avec les deux -O3et -O2 -fvia-C, dans environ 18,3 secondes.
Wile E. Coyote, le
3

Python - 41 caractères

499 chiffres

x=3;exec'x=pow(3,x,10**500);'*500;print x

500 chiffres

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+`x`
grignoteur
la source
1
Vous utilisez la connaissance que le 500ème chiffre de l'arrière est un 0. Cela donnerait la mauvaise réponse pour, disons, 200.
1
@Tim Le problème demande "200 chiffres ou plus". Il suffit de coder en dur un décompte qui fonctionne et d'en finir. (ou laissez-le en tant que tel: il imprime 499 chiffres et c'est assez bon pour la question posée)
JB
@JB: Bien sûr, je serais satisfait du 499 si le 0 était omis. Maintenant, cependant, il suppose qu'un chiffre spécifique est 0.
@ user475 - Par les propriétés des tours électriques, si vous calculez les derniers (d) chiffres et que le résultat est inférieur à (d) chiffres, alors les chiffres manquants (à gauche) doivent être des "0". Il est donc correct d'ajouter le chiffre «0» manquant, mais cela doit être fait en examinant la longueur du résultat et en ajoutant le nombre approprié de «0».
Kevin Fegan
3

Python - 62 59 55 caractères

x=3
for i in range(500):x=pow(3,x,10**500)
print"0%d"%x

Prend environ 12 secondes sur mon PC.

sh-3.1$ time python cg_graham.py
02425950695064738395657479136519351798334535362521430035401260267716226721604198
10652263169355188780388144831406525261687850955526460510711720009970929124954437
88874960628829117250630013036229349160802545946149457887142783235082924210209182
58967535604308699380168924988926809951016905591995119502788717830837018340236474
54888222216157322801013297450927344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380032223487239670184851864390591
04575627262464195387

real    0m11.807s
user    0m0.000s
sys     0m0.015s
sh-3.1$
Wile E. Coyote
la source
3
Le powmod natif est un tueur :-)
JB
Vous pouvez utiliser10**500
gnibbler
@JB, c'est la seule raison pour laquelle j'ai utilisé Python pour cette entrée :)
Wile E. Coyote
@gnibbler, mis à jour, merci! Je suis nouveau sur Python :)
Wile E. Coyote
0

Axiome, 63 octets

f()==(r:=3;d:=10^203;for i in 1..203 repeat r:=powmod(3,r,d);r)

ungolf et résultat

--This find the Graham's number follow the algo found in wiki
--http://en.wikipedia.org/wiki/Graham%27s_number
ff()==
   r:=3; d:=10^203
   for i in 1..203 repeat r:=powmod(3,r,d)
   r

(3) -> a:=f()::String
   (3)
  "8871783083701834023647454888222216157322801013297450927344594504343300901096
  92802535275183328988446150894042482650181938515625357963996189939679054966380
  03222348723967018485186439059104575627262464195387"
                                                             Type: String
(4) -> #a
   (4)  203
                                                    Type: PositiveInteger

# a = 203 signifie que le nombre len est> 200 il pense aussi qu'il n'a pas de 0 en premier ...

RosLuP
la source
0

Headsecks, 602 octets

(h@HP0&Y+h8h (hx0RWc@4vYcx#@#PJ"B?[#CPx (h Lx$2(pl2YL;KD:T{9$2j<
 LSSh,ZT l2I<Pp,@4SX`,:xtc@T",($)<cKT\lbBAy44,dQl[yL"l+i,;9<*j0P
|)lD[+`\RBi!< LaD(LHPLyt{{@\iADRQdHTZQIT3[X`DB*`X$Cxh$*(T0$| ,[;
4:bit0DqAqi!lCYQ)<Ad(|1<$R4l+#tZrLPDatC[d*@0pDclJbh0|#S9<JRy!TP0
D+!|qiTXp<r$##Atj,B1ts;HLJ"Xp44I4cK4@|Q,4JI$|hp$Zyd+yl:y<s#\pD:9
4RDK,A!<X \cqLZ" h,kHp|qLRQIDh,+StZbL+{(|jqqL;9L"(xd"<s$8\:x,CY\
z0T[,(XdcxlbaD*D;+tDj\JIi4k[)LPDLBzP@DSc$jL $s4BjQ19|;!)|9t;TaQA
dLzit[0@l2!)I$,0P@$y<L4pLPLStQT"!a| $+8(DZ`00t ,RtX4C@$yQ11|KI\"
`|2<k3|R(Dyi<)LshTrzQ$sp D+DRbH|Q$CqT0D;AA\jdXd"ppdK3LzZl#\Bl`@t
k$*,11qTK+Xp|rqDZXp4{C!<Y4

Imprime les 200 derniers chiffres.

Veuillez supprimer les sauts de ligne avant de lancer.

Esolanging Fruit
la source
Comment sommes-nous censés le faire fonctionner?
caird coinheringaahing
Absolument aucune idée (je viens de le traduire de BF). Mais j'ai cherché "headecks" sur github et il semble qu'il y ait quelques implémentations (bien que le lien d'implémentation de référence semble être mort).
Esolanging Fruit