Calcular os últimos dígitos do número de Graham

13

O número de Graham termina em 7. É um número massivo, em teoria exigindo mais informações para armazenar do que o tamanho do próprio universo. No entanto, é possível calcular os últimos dígitos do número de Graham.

Os últimos dígitos são:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Seu programa não pode conter esses (ou números semelhantes), mas deve calculá-los. Ele deve calcular 200 dígitos ou mais.

Saída para stdout. Tempo de execução de no máximo 2 minutos em hardware decente. O programa mais curto vence.

Thomas O
fonte
Quantos dígitos devem ser impressos?
Dogbert
@Dogbert D'oh. Eu senti falta disso. 200 ou mais seria bom.
Thomas O
Ruby não vai mesmo calcular 3**7625597484987enquanto Python faz :)
gnibbler
@gnibbler, umm como? o resultado teria mais de 3 trilhões de dígitos.
9788 Dogbert
1
@ Dogbert, dada a memória e o tempo suficientes, o Python irá em frente e o calculará usando seus longos. Ruby nem faz 3 ** 5000000. parece ter algum tipo de limite de lá
gnibbler

Respostas:

9

dc - 21 caracteres

[3z202>xO200^|]dsxxrp

Isso leva cerca de um minuto no meu computador e levaria muito mais tempo para valores maiores que 200. Não gera zeros à esquerda.

Aqui está uma versão um pouco mais longa, mas mais rápida (26 caracteres):

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

Haskell, 99

O desempenho não é estelar, mas ele consegue calcular 500 dígitos em um minuto no meu hardware de uma década.

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, eu adoraria ouvir sobre seu desempenho em hardware mais moderno)

JB
fonte
Demora cerca de 19 segundos para executar no meu PC. Em uma nota lateral, isso não imprime um 0 inicial antes da saída.
Dogbert
Sim, é buggy em todas as contagens de dígitos com zeros à esquerda. Basta calcular para 501 ;-) Obrigado pela referência. Você o executou interpretado ou compilado?
JB
Eu compilei com ghc -o g.exe g.hs. Não tenho certeza se essa é a melhor maneira de compilar.
Dogbert
Acabei de executar ghc -O3 graham.hs As opções recomendadas pelo médico on-line parecem ser -O2 -fvia-C. (e parece que minha GHC é alguns lançamentos por trás já)
JB
Parece estar rodando na mesma velocidade com ambos -O3e -O2 -fvia-C, em cerca de 18,3 segundos.
Dogbert
3

Python - 41 caracteres

499 dígitos

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

500 dígitos

x=3;exec'x=pow(3,x,10**500);'*500;print'0'+`x`
mordedor
fonte
1
Você está usando o conhecimento de que o 500º dígito da parte traseira é um 0. Daria a resposta errada para, digamos, 200. #
1
@ Tim O problema pede "200 dígitos ou mais". Basta codificar uma contagem que funcione e que seja feita com ela. (ou deixá-lo como tal: ele imprime 499 dígitos e isso é bom o suficiente para a pergunta como pediu)
JB
@JB: Claro, eu ficaria satisfeito com o 499 se o 0 fosse deixado de fora. Agora, porém, ele assume que um dígito específico é 0.
@ user475 - Pelas propriedades das torres de energia, se você estiver calculando os últimos (d) dígitos e o resultado for menor que (d) dígitos, os dígitos ausentes (à esquerda) devem ser "0". Portanto, não há problema em adicionar o dígito "0" ausente, mas isso deve ser feito examinando a duração do resultado e adicionando o número apropriado de "0".
precisa
3

Python - 62 59 55 caracteres

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

Demora cerca de 12 segundos no meu 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$
Dogbert
fonte
3
O powmod nativo é um assassino :-)
JB
Você pode usar10**500
gnibbler
@JB, que é a única razão que eu usei Python para esta entrada :)
Dogbert
@gnibbler, atualizado, obrigado! Eu sou novo para Python :)
Dogbert
0

Axioma, 63 bytes

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

ungolf e resultado

--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 significa que o número len é> 200, mas também não possui 0 primeiro ...

RosLuP
fonte
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

Imprime os últimos 200 dígitos.

Remova as novas linhas antes de executar.

Esolanging Fruit
fonte
Como devemos executá-lo?
caird coinheringaahing
Absolutamente nenhuma idéia (acabei de traduzir isso de BF). Mas eu procurei "headsecks" no github e parece que existem algumas implementações (embora o link de implementação de referência pareça estar morto).
Esolanging Fruit