Berechnen Sie die letzten Ziffern von Grahams Zahl

13

Grahams Zahl endet mit einer 7. Es ist eine massive Zahl, für deren Speicherung theoretisch mehr Informationen erforderlich sind als die Größe des Universums. Es ist jedoch möglich, die letzten Ziffern von Grahams Nummer zu berechnen.

Die letzten Ziffern sind:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Ihr Programm darf diese (oder ähnliche) Zahlen nicht enthalten, muss sie aber berechnen. Es muss 200 Stellen oder mehr berechnen.

Ausgabe auf Standardausgabe. Laufzeit von maximal 2 Minuten auf anständiger Hardware. Kürzeste Sendung gewinnt.

code-golf number Thomas O.
quelle
Wie viele Ziffern sollen gedruckt werden?
Dogbert
@Dogbert D'oh. Das habe ich vermisst. 200 oder mehr wäre in Ordnung.
Thomas O
Ruby wird nicht einmal berechnen, 3**7625597484987während Python tut :)
Gnibbler
@knabber, ähm wie? das Ergebnis hätte mehr als 3 Billionen Stellen.
Dogbert
1
@Dogbert, wenn genügend Speicher und Zeit zur Verfügung stehen, berechnet Python die Länge. Ruby macht nicht einmal 3 ** 5000000. scheint eine Art Limit zu haben
Gnibbler

Antworten:

9

DC - 21 Zeichen

[3z202>xO200^|]dsxxrp

Dies dauert auf meinem Computer ungefähr eine Minute und würde bei Werten über 200 erheblich länger dauern. Führende Nullen werden nicht ausgegeben.

Hier ist eine etwas längere, aber schnellere Version (26 Zeichen):

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

Haskell, 99

Leistung ist nicht herausragend, schafft es aber, auf meiner jahrzehntealten Hardware in einer Minute 500 Stellen zu berechnen.

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

(Übrigens, ich würde gerne etwas über die Leistung auf moderner Hardware erfahren.)

JB
quelle
Die Ausführung auf meinem PC dauert ungefähr 19 Sekunden. Nebenbei bemerkt wird vor der Ausgabe keine führende 0 ausgegeben.
Dogbert
Ja, es ist fehlerhaft in allen Ziffern mit führenden Nullen. Rechne einfach für 501 ;-) Danke für den Benchmark. Hast du es interpretiert oder kompiliert?
JB
Ich habe es mit kompiliert ghc -o g.exe g.hs. Ich bin mir nicht sicher, ob dies der beste Weg ist, um zu kompilieren.
Dogbert
Ich habe gerade ghc -O3 graham.hs die empfohlenen Badass-Optionen aus dem Online-Dokument ausgeführt -O2 -fvia-C. (und es sieht so aus, als ob mein GHC bereits ein paar Veröffentlichungen hinter sich hat)
JB
Es scheint mit beiden -O3und -O2 -fvia-Cin ungefähr 18,3 Sekunden mit der gleichen Geschwindigkeit zu laufen .
Dogbert
3

Python - 41 Zeichen

499 Stellen

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

500 Stellen

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+`x`
Knabberzeug
quelle
1
Sie verwenden das Wissen, dass die 500. Stelle von hinten eine 0 ist. Es würde die falsche Antwort für beispielsweise 200 geben.
1
@Tim Das Problem fragt nach "200 Stellen oder mehr". Einfach eine Zählung fest programmieren, die funktioniert und fertig ist. (oder lassen Sie es so: Es druckt 499 Ziffern und das ist gut genug für die gestellte Frage)
JB
@JB: Sicher, ich wäre mit der 499 zufrieden, wenn die 0 weggelassen würde. Jetzt wird jedoch davon
@ user475 - Wenn Sie nach den Eigenschaften von Power-Towers die letzten (d) Ziffern berechnen und das Ergebnis kleiner als (d) Ziffern ist, müssen die fehlenden Ziffern (links) "0" sein. Es ist also in Ordnung, die fehlende Ziffer "0" hinzuzufügen. Sie sollten jedoch die Länge des Ergebnisses untersuchen und die entsprechende Anzahl von "0" hinzufügen.
Kevin Fegan
3

Python - 62 59 55 Zeichen

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

Dauert auf meinem PC ungefähr 12 Sekunden.

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$
Dogbert
quelle
3
Der gebürtige Powmod ist ein Killer :-)
JB
Sie können10**500
gnibbler
@JB, das ist der einzige Grund, warum ich Python für diesen Eintrag verwendet habe :)
Dogbert
@ Gnibbler, aktualisiert, danke! Ich bin neu in Python :)
Dogbert
0

Axiom, 63 Bytes

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

ungolf und ergebnis

--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 bedeutet, dass die Anzahl len> 200 ist. Es wird auch darauf hingewiesen, dass es zuerst keine 0 gibt.

RosLuP
quelle
0

Headsecks, 602 Bytes

(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

Druckt die letzten 200 Ziffern.

Bitte entfernen Sie die Zeilenumbrüche, bevor Sie loslegen.

Esolanging Fruit
quelle
Wie sollen wir das machen?
Caird Coinheringaahing
Absolut keine Ahnung (ich habe das gerade von BF übersetzt). Aber ich habe "headsecks" auf github gesucht und es sieht so aus, als gäbe es ein paar Implementierungen (obwohl der Link zur Referenzimplementierung tot zu sein scheint).
Esolanging Fruit