Hitung digit terakhir dari Nomor Graham

13

Angka Graham berakhir dengan angka 7. Ini adalah angka yang sangat besar, secara teori membutuhkan lebih banyak informasi untuk disimpan daripada ukuran alam semesta itu sendiri. Namun dimungkinkan untuk menghitung beberapa digit terakhir dari nomor Graham.

Beberapa digit terakhir adalah:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Program Anda mungkin tidak mengandung ini (atau nomor yang serupa), tetapi harus menghitungnya. Harus menghitung 200 digit atau lebih.

Output ke stdout. Waktu berjalan maksimal 2 menit pada perangkat keras yang layak. Kemenangan program terpendek.

code-golf number Thomas O
sumber
Berapa banyak digit yang harus dicetak?
Wile E. Coyote
@Dogbert D'oh. Saya melewatkan itu. 200 atau lebih akan baik-baik saja.
Thomas O
Ruby bahkan tidak akan menghitung 3**7625597484987sedangkan Python melakukannya :)
gnibbler
@gnibbler, umm bagaimana? hasilnya akan memiliki lebih dari 3 triliun digit.
Wile E. Coyote
1
@ Dogbert, mengingat cukup memori dan waktu Python akan melanjutkan menghitung menggunakan longs itu. Ruby bahkan tidak mau melakukan 3 ** 5000000. tampaknya memiliki semacam batasan di sana
gnibbler

Jawaban:

9

dc - 21 karakter

[3z202>xO200^|]dsxxrp

Ini membutuhkan waktu sekitar satu menit di komputer saya, dan akan membutuhkan waktu lebih lama untuk nilai yang lebih besar dari 200. Tidak menghasilkan angka nol terkemuka.

Ini versi yang sedikit lebih panjang tetapi lebih cepat (26 karakter):

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

Haskell, 99

Performanya tidak luar biasa, tetapi ia berhasil menghitung 500 digit dalam satu menit pada perangkat keras saya yang berusia satu dekade.

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, saya ingin mendengar tentang kinerjanya pada perangkat keras yang lebih modern)

JB
sumber
Butuh sekitar 19 detik untuk berjalan di PC saya. Di samping catatan, ini tidak mencetak awalan 0 sebelum output.
Wile E. Coyote
Yup, itu buggy pada semua jumlah digit dengan nol terkemuka. Hitung saja untuk 501 ;-) Terima kasih atas tolok ukurnya. Apakah Anda menjalankannya ditafsirkan atau dikompilasi?
JB
Saya kompilasi dengan ghc -o g.exe g.hs. Tidak yakin apakah itu cara terbaik untuk kompilasi.
Wile E. Coyote
Saya baru saja menjalankan ghc -O3 graham.hs Opsi badass yang disarankan dari dokumen online -O2 -fvia-C. (dan sepertinya GHC saya sudah beberapa rilis di belakang)
JB
Tampaknya berjalan pada kecepatan yang sama dengan keduanya -O3dan -O2 -fvia-C, dalam waktu sekitar 18,3 detik.
Wile E. Coyote
3

Python - 41 karakter

499 digit

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

500 digit

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+`x`
gnibbler
sumber
1
Anda menggunakan pengetahuan bahwa digit ke-500 dari belakang adalah angka 0. Ini akan memberikan jawaban yang salah untuk, katakanlah, 200.
1
@ Tim Masalahnya meminta "200 digit atau lebih". Hanya hardcode hitungan yang berfungsi dan selesai dengannya. (atau biarkan seperti itu: ia mencetak 499 digit dan itu cukup baik untuk pertanyaan yang diajukan)
JB
@ JK: Tentu, saya akan puas dengan 499 jika 0 ditinggalkan. Namun, sekarang diasumsikan bahwa angka tertentu adalah 0.
@ user475 - Berdasarkan properti menara listrik, jika Anda menghitung digit (d) terakhir, dan hasilnya kurang dari (d) digit, maka digit yang hilang (di sebelah kiri) haruslah "0". Jadi tidak apa-apa untuk menambahkan digit "0" yang hilang, tetapi harus dilakukan dengan memeriksa panjang hasilnya dan menambahkan angka "0" yang sesuai.
Kevin Fegan
3

Python - 62 59 55 karakter

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

Membutuhkan waktu sekitar 12 detik di PC saya.

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
sumber
3
Powmod asli adalah pembunuh :-)
JB
Anda dapat menggunakan10**500
gnibbler
@ JP, itulah satu-satunya alasan saya menggunakan Python untuk entri ini :)
Wile E. Coyote
@gnibbler, diperbarui, terima kasih! Saya baru mengenal Python :)
Wile E. Coyote
0

Aksioma, 63 byte

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

ungolf dan hasilnya

--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 berarti angka len adalah> 200 itu menas juga bahwa ia tidak memiliki 0 pertama ...

RosLuP
sumber
0

Headecks, 602 byte

(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

Mencetak 200 digit terakhir.

Harap hapus baris baru sebelum berjalan.

Buah Esolanging
sumber
Bagaimana kita menjalankannya?
caird coinheringaahing
Sama sekali tidak tahu (saya baru menerjemahkan ini dari BF). Tapi saya mencari "headecks" di github dan sepertinya ada beberapa implementasi (meskipun tautan implementasi referensi tampaknya sudah mati).
Buah Esolanging