Рассчитать последние цифры числа Грэма

13

Число Грэма оканчивается на 7. Это огромное число, теоретически требующее хранения большего количества информации, чем размер самой вселенной. Однако возможно вычислить последние несколько цифр числа Грэма.

Последние несколько цифр:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Ваша программа может не содержать эти (или аналогичные числа), но должна их вычислять. Он должен рассчитывать 200 цифр или более.

Вывод на стандартный вывод. Время работы максимум 2 минуты на приличном оборудовании. Кратчайшая программа выигрывает.

code-golf number Томас О
источник
Сколько цифр должно быть напечатано?
Уайл Э. Койот
@ Dogbert D'oh. Я пропустил это. 200 или больше было бы хорошо.
Томас О,
Ruby даже не рассчитывает, в 3**7625597484987то время как Python делает :)
gnibbler
@gnibbler, ммм как? результат будет иметь более 3 триллионов цифр.
Уайл Э. Койот
1
@ Догберт, учитывая достаточное количество памяти и времени, Python рассчитывает, используя его longs. Руби даже не сделает 3 ** 5000000. там, кажется, есть какой-то предел
gnibbler

Ответы:

9

постоянный ток - 21 символ

[3z202>xO200^|]dsxxrp

На моем компьютере это займет около минуты и займет намного больше времени для значений, превышающих 200. Он не выводит начальные нули.

Вот немного более длинная, но более быстрая версия (26 символов):

[3rAz^|dz205>x]dsxxAz6-^%p
3[3rAz^|dz202>x]dsxxAz3-^%p # or an extra character for a few less iterations
Nabb
источник
4

Хаскелл, 99

Производительность не звездная, но мне удается вычислить 500 цифр в минуту на моем десятилетнем оборудовании.

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

(кстати, я бы хотел услышать о его производительности на более современном оборудовании)

JB
источник
Требуется приблизительно 19 секунд, чтобы бежать на моем компьютере. На заметку о том, что перед выводом не выводится начальный 0.
Уайл Э. Койот
Да, это глючит на всех цифрах с ведущими нулями. Просто посчитайте за 501 ;-) Спасибо за тест. Вы запустили интерпретированный или скомпилированный файл?
JB
Я скомпилировал это с ghc -o g.exe g.hs. Не уверен, что это лучший способ компиляции.
Уайл Э. Койот
Я только что запустил ghc -O3 graham.hs рекомендуемые варианты из онлайн-документа -O2 -fvia-C. (и, похоже, мой GHC уже вышел на несколько релизов)
JB
Похоже, что он работает с одинаковой скоростью -O3и -O2 -fvia-Cпримерно за 18,3 секунды.
Уайл Э. Койот
3

Питон - 41 символ

499 цифр

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

500 цифр

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+`x`
gnibbler
источник
1
Вы используете знание, что 500-ая цифра сзади равна 0. Это даст неправильный ответ, скажем, для 200.
1
@Tim Проблема требует "200 цифр или больше". Просто закодируйте счетчик, который работает, и с этим покончено. (или оставьте это так: он печатает 499 цифр, и этого вполне достаточно для заданного вопроса)
JB
@JB: Конечно, я был бы доволен 499, если бы 0 было опущено. Теперь, однако, предполагается, что конкретная цифра равна 0.
@ user475 - Если вы вычисляете последние (d) цифры, а в результате вы получите последние цифры (d), а пропущенные цифры (слева) должны быть равны «0». Поэтому можно добавить недостающую цифру «0», но это следует сделать, изучив длину результата и добавив соответствующее число «0».
Кевин Феган
3

Python - 62 59 55 символов

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

Занимает около 12 секунд на моем компьютере.

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$
Уайл Э. Койот
источник
3
Native powmod - убийца :-)
JB
Вы можете использовать10**500
gnibbler
@JB, это единственная причина, по которой я использовал Python для этой записи :)
Wile E. Coyote
@gnibbler, обновлено, спасибо! Я новичок в Python :)
Wile E. Coyote
0

Аксиома, 63 байта

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

разгул и результат

--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 означает, что число len> 200, это также означает, что у него сначала нет нуля ...

RosLuP
источник
0

Headsecks, 602 байта

(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

Печать последних 200 цифр.

Пожалуйста, удалите символы новой строки перед запуском.

Esolanging Fruit
источник
Как мы должны управлять этим?
Кэрд coinheringaahing
Абсолютно не знаю (я только что перевел это из BF). Но я искал "headsecks" на github и похоже, что есть несколько реализаций (хотя ссылка на эталонную реализацию кажется мертвой).
Esolanging Fruit