Calcular los últimos dígitos del número de Graham

13

El número de Graham termina en 7. Es un número masivo, que en teoría requiere más información para almacenar que el tamaño del universo mismo. Sin embargo, es posible calcular los últimos dígitos del número de Graham.

Los últimos dígitos son:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Es posible que su programa no contenga estos (o números similares), pero debe calcularlos. Debe calcular 200 dígitos o más.

Salida a stdout. Tiempo de ejecución de un máximo de 2 minutos en hardware decente. El programa más corto gana.

Thomas O
fuente
¿Cuántos dígitos se deben imprimir?
Wile E. Coyote
@Dogbert D'oh. Me lo perdí. 200 o más estaría bien.
Thomas O
Ruby ni siquiera calculará 3**7625597484987mientras que Python sí :)
gnibbler
@gnibbler, umm ¿cómo? el resultado tendría más de 3 billones de dígitos.
Wile E. Coyote
1
@Dogbert, dada suficiente memoria y tiempo, Python seguirá adelante y lo calculará usando sus largos. Ruby ni siquiera hará 3 ** 5000000. parece tener algún tipo de límite de ahí
gnibbler

Respuestas:

9

dc - 21 caracteres

[3z202>xO200^|]dsxxrp

Esto toma aproximadamente un minuto en mi computadora, y tomaría mucho más tiempo para valores mayores a 200. No genera ceros iniciales.

Aquí hay una versión un poco más larga pero más 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
fuente
4

Haskell, 99

El rendimiento no es estelar, pero logra calcular 500 dígitos en un minuto en mi hardware de una 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

(por cierto, me encantaría saber sobre su rendimiento en hardware más moderno)

JB
fuente
Tarda unos 19 segundos en ejecutarse en mi PC. En una nota al margen, esto no imprime un 0 inicial antes de la salida.
Wile E. Coyote
Sí, tiene errores en todos los recuentos de dígitos con ceros a la izquierda. Solo calcule para 501 ;-) Gracias por el punto de referencia. ¿Lo ejecutaste interpretado o compilado?
JB
Lo compilé con ghc -o g.exe g.hs. No estoy seguro si esa es la mejor manera de compilar.
Wile E. Coyote
Acabo de ejecutar ghc -O3 graham.hs Las opciones recomendadas del documento en línea parecen ser -O2 -fvia-C. (y parece que mi GHC ya tiene algunos lanzamientos atrás)
JB
Parece estar funcionando a la misma velocidad con ambos -O3y -O2 -fvia-C, en unos 18,3 segundos.
Wile E. Coyote
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`
gnibbler
fuente
1
Está utilizando el conocimiento de que el dígito número 500 del reverso es un 0. Daría la respuesta incorrecta para, digamos, 200.
1
@Tim El problema pide "200 dígitos o más". Simplemente codifique un recuento que funcione y termine con él. (o déjelo como tal: imprime 499 dígitos y eso es lo suficientemente bueno para la pregunta que se le hizo)
JB
@JB: Claro, estaría satisfecho con el 499 si se dejara el 0. Ahora, sin embargo, se supone que un dígito específico es 0.
@ user475: según las propiedades de las torres de energía, si está calculando los últimos (d) dígitos y el resultado es menor que (d) dígitos, los dígitos que faltan (a la izquierda) deben ser "0". Por lo tanto, está bien agregar el dígito "0" que falta, pero debe hacerse examinando la longitud del resultado y agregando el número apropiado de "0".
Kevin Fegan
3

Python - 62 59 55 caracteres

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

Toma alrededor de 12 segundos en mi 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$
Wile E. Coyote
fuente
3
Powmod nativo es un asesino :-)
JB
Puede usar10**500
gnibbler
@JB, esa es la única razón por la que usé Python para esta entrada :)
Wile E. Coyote
@gnibbler, actualizado, ¡gracias! Soy nuevo en Python :)
Wile E. Coyote
0

Axioma, 63 bytes

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

ungolf y 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 el número de len es> 200 también menas que no tiene un 0 primero ...

RosLuP
fuente
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 los últimos 200 dígitos.

Por favor, elimine las nuevas líneas antes de ejecutar.

Fruta Esolanging
fuente
¿Cómo se supone que debemos ejecutarlo?
caird coinheringaahing
Absolutamente ninguna idea (acabo de traducir esto de BF). Pero busqué "headsecks" en github y parece que hay algunas implementaciones (aunque el enlace de implementación de referencia parece estar muerto).
Esolanging Fruit