Calculate the last digits of Graham's Number

Graham's number ends in a 7. It is a massive number, in theory requiring more information to store than the size of the universe itself. However it is possible to calculate the last few digits of Graham's number.

The last few digits are:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Your program may not contain these (or similar numbers), but must calculate them. It must calculate 200 digits or more.

Output to stdout. Running time of a maximum of 2 minutes on decent hardware. Shortest program wins.

• How many digits should be print? Feb 8 '11 at 19:54
• @Dogbert D'oh. I missed that. 200 or more would be fine. Feb 8 '11 at 20:31
• Ruby won't even calculate 3**7625597484987 whereas Python does :) Feb 8 '11 at 22:36
• @gnibbler, umm how? the result would have more than 3 trillion digits. Feb 9 '11 at 9:53
• @Dogbert, given enough memory and time Python will go ahead an calculate it using it's longs. Ruby won't even do 3**5000000. seems to have some sort of limit in there Feb 9 '11 at 12:27

dc - 21 chars

[3z202>xO200^|]dsxxrp

This takes about a minute on my computer, and would take lots longer for values larger than 200. It doesn't output leading zeroes.

Here's a slightly longer but faster version (26 chars):

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

Performance not stellar, but it manages to compute 500 digits in a minute on my decade-old hardware.

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, I'd love to hear about its performance on more modern hardware)

• Takes about 19 seconds to run on my PC. On a side note, this doesn't print a leading 0 before the output. Feb 8 '11 at 21:29
• Yup, it's buggy on all digit counts with leading zeros. Just compute for 501 ;-) Thanks for the benchmark. Did you run it interpreted or compiled?
– J B
Feb 8 '11 at 21:32
• I compiled it with ghc -o g.exe g.hs. Not sure if that's the best way to compile. Feb 8 '11 at 21:34
• I just ran ghc -O3 graham.hs The recommended badass options from the online doc seem to be -O2 -fvia-C. (and it looks like my GHC is a few releases behind already)
– J B
Feb 8 '11 at 21:41
• It seems to be running at the same speed with both -O3 and -O2 -fvia-C, in around 18.3 seconds. Feb 8 '11 at 23:15

Python - 41 chars

499 digits

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

500 digits

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+x
• You are using the knowledge that the 500th digit from the back is a 0. It would give the wrong answer for, say, 200.
– user475
Feb 9 '11 at 8:16
• @Tim The problem asks for "200 digits or more". Just hardcode a count that works and be done with it. (or leave it as such: it prints 499 digits and that's good enough for the question as asked)
– J B
Feb 9 '11 at 8:51
• @J B: Sure, I'd be satisfied with the 499 if the 0 was left out. Now, however, it assumes that a specific digit is 0.
– user475
Feb 9 '11 at 9:01
• @user475 - By the properties of power-towers, if you are calculating the last (d) digits, and the result is less than (d) digits, then the missing digits (on the left) must be "0's". So it's OK to add the missing "0" digit, but it should be done by examining the length of the result and adding the appropriate number of "0's". Jul 14 '13 at 20:07

Python - 6259 55 chars

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

Takes around 12 seconds on my 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$
• Native powmod is a killer :-)
– J B
Feb 8 '11 at 21:24
• You can use 10**500 Feb 8 '11 at 22:50
• @J B, that's the only reason I used Python for this entry :) Feb 8 '11 at 23:22
• @gnibbler, updated, thanks! I'm new to Python :) Feb 8 '11 at 23:23

Axiom, 63 bytes

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

ungolf and result

--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 means the number len is >200 it menas too that it not has some 0 first...

(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[XDB*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(DZ00t ,RtX4C@$yQ11|KI\" |2<k3|R(Dyi<)LshTrzQ$sp D+DRbH|Q$CqT0D;AA\jdXd"ppdK3LzZl#\Bl`@t k$*,11qTK+Xp|rqDZXp4{C!<Y4