Teóricamente muestra el número de Graham

44

El número de Graham Gse define de esta manera:

u(3,n,1) = 3^n
u(3,1,m) = 3
u(3,n,m) = u(3,u(3,n-1,m),m-1)
[Knuth's up-arrow notation]
[Conway chained arrow notation]

THEN

g1 = u(3,3,4)
g2 = u(3,3,g1)
g3 = u(3,3,g2)
...
G = u(3,3,g63)

Se le da eso u(3,3,2)=7625597484987para verificar su código.

Su tarea es escribir un programa / función que genere el valor de forma Gdeterminista, dado el tamaño entero suficiente y el tiempo suficiente.

Referencias

Tabla de clasificación

Mostrar fragmento de código

code-golf number-theory Monja permeable
fuente
2
Relacionados .
Monja Leaky
77
¿Se permite la aleatoriedad? Si solo produzco valores aleatorios, eventualmente se debe producir el número de Graham.
millas
15
@miles ¿Por qué demonios ya no es una escapatoria estándar? Aclarado
Leaky Nun
18
Advertencia: u (3, 3, 2) = u (3, 2, 3) = 7625597484987, por lo que también querrá probar otros valores como u (3, 5, 1) = 243 para asegurarse de que tiene El argumento es correcto.
Anders Kaseorg
2
¿El número de Graham?
Beta Decay

Respuestas:

48

Cálculo binario lambda , 114 bits = 14.25 bytes

Hexdump:

00000000: 4457 42b0 2d88 1f9d 740e 5ed0 39ce 80    DWB.-...t.^.9..

Binario:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Explicación

01 00                                           (λx.
│    01 00                                        (λy.
│    │    01 01 01 110                              x
│    │    │  │  └─ 10                               y
│    │    │  └─ 00                                  (λm.
│    │    │       01 01 01 10                         m
│    │    │       │  │  └─ 00                         (λg.
│    │    │       │  │       00                         λn.
│    │    │       │  │         01 01 10                  n
│    │    │       │  │         │  └─ 110                 g
│    │    │       │  │         └─ 00                     (λz.
│    │    │       │  │              10                     z))
│    │    │       │  └─ 00                            (λn.
│    │    │       │       00                            λf.
│    │    │       │         01 111110                    x
│    │    │       │         └─ 01 110                    (n
│    │    │       │            └─ 10                      f))
│    │    │       └─ 1110                             x)
│    │    └─ 10                                     y)
│    └─ 00                                        (λf.
│         00                                        λz.
│           01 110                                   f
│           └─ 01 01 1110                            (x
│              │  └─ 110                              f
│              └─ 10                                  z)))
└─ 00                                           (λf.
     00                                           λz.
       01 110                                      f
       └─ 01 110                                   (f
          └─ 01 110                                 (f
             └─ 10                                   z)))

Esto es (λ x . (Λ y . X y (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . X ( n f )) x ) y ) (λ f . Λ z . f ( x f z ))) 3, donde todos los números se representan como números de la Iglesia. Números Iglesia son la representación lambda cálculo estándar de los números naturales, y están bien adaptados a este problema debido a que un número Iglesia se define por iteración función: n g es el n º iterate de la función g .

Por ejemplo, si g es la función λ n . λ f . 3 ( n f ) que multiplica 3 por un número de Iglesia, luego λ n . n g 1 es la función que lleva 3 al poder de un número de Iglesia. Iterar esta operación m veces da

m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) n = u (3, n , m ).

(Usamos la multiplicación u (-, -, 0) en lugar de la exponenciación u (-, -, 1) como el caso base, porque restar 1 del número de la Iglesia es desagradable ).

Sustituir n = 3:

m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3 = u (3, 3, m ).

Iterar esa operación 64 veces, comenzando en m = 4, da

64 (λ m . M (λ g . Λ n . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .

Para optimizar esta expresión, sustituya 64 = 4 ^ 3 = 3 4:

3 4 (λ m . M (λ g λ. N . N g 1) (λ n . Λ f . 3 ( n f )) 3) 4 = G .

Recuerde 4 = succ 3 = λ f . λ z . f (3 f z ) como argumento lambda:

(λ y . 3 y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . 3 ( n f )) 3) y ) (λ f . λ z . f (3 f z )) = G .

Finalmente, recuerde 3 = λ f . λ z . f ( f ( f z )) como argumento lambda:

(λ x . (λ y . x y (λ m . m (λ g . λ n . n g 1) (λ n . λ f . x ( n f )) x ) y ) (λ f . λ z . f ( x f z ))) 3 = G .

Anders Kaseorg
fuente
¿Dónde se puede encontrar un intérprete para este idioma?
Dennis
44
@Dennis tromp.github.io/cl/cl.html tiene un par de ellas.
Anders Kaseorg
1
Esto es increíble . esto merece una recompensa considerable
gato
1
14.25 bytesparece estar arruinando la clasificación. Se analiza como 25 bytesy, por lo tanto, se coloca como segundo.
Dan
1
@Dan, arreglé el fragmento de la tabla de clasificación, creo.
Anders Kaseorg
40

Haskell, 41 bytes

i=((!!).).iterate
i(($3).i(`i`1)(*3))4 64

Explicación:

(`i`1)f n= i f 1 ncalcula la niteración de la función fcomenzando en 1. En particular, (`i`1)(*3)n= 3 ^ n , e iterar esta construcción m veces da i(`i`1)(*3)m n= u (3, n , m ). Podemos reescribir eso como (($n).i(`i`1)(*3))m= u (3, n , m ) e iterar esta construcción k veces para obtener i(($3).i(`i`1)(*3))4 k= g _ k .

Anders Kaseorg
fuente
16

Haskell, 43 bytes

q=((!!).).iterate
g=q(`q`1)(3*)
q(`g`3)4$64

Debe haber una mejor manera de voltear en glínea.

46 bytes:

i=iterate
n%0=3*n
n%m=i(%(m-1))1!!n
i(3%)4!!64

48 bytes:

n%1=3^n
1%m=3
n%m=(n-1)%m%(m-1)
iterate(3%)4!!64

Simplemente escribiendo las definiciones.

Los casos base son un poco más limpios respaldados hasta 0, aunque no guarda bytes. Quizás sea más fácil escribir una definición alternativa.

n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1
xnor
fuente
¿Puedes usar otra función que tenga una precedencia menor que +para eliminar los paréntesis m-1?
Leaky Nun
Cuento 44 bytes, ¿y qué pasó con 4 y 64?
Leaky Nun
Vaya, copié en mi prueba de parámetros más pequeños. No creo que pueda cambiar la precedencia del operador porque estoy definiendo una nueva función y esas tienen una precedencia predeterminada. No puedo sobrescribir una función existente.
xnor
Quiero decir, cuento 44 bytes después de que lo vuelves a cambiar a 64.
Leaky Nun
Creo que quieres decir (`g`3), no (3`g`).
Anders Kaseorg
10

Pyth, 25 bytes

M?H.UgbtH*G]3^3Gug3tG64 4

La primera parte M?H.UgbtH*G]3^3Gdefine un método g(G,H) = u(3,G,H+1).

Para probar la primera parte, comprobar que 7625597484987=u(3,3,2)=g(3,1): g3 1.

La segunda parte ug3tG64 4comienza desde r0 = 4y luego computa rn = u(3,3,r(n-1)) = g(3,r(n-1))64 veces, generando el valor final ( rse elige en lugar de gevitar confusiones).

Para probar esta parte, empezar desde r0=2y luego calcular r1: ug3tG1 2.

Monja permeable
fuente
Si g (G, H) = u (3, G, H + 1), debe tener r (n) = u (3, 3, r (n - 1)) = g (3, r (n - 1) ) - 1), no g (3, r (n - 1)). Creo que su código es correcto, pero a su explicación le falta el 1.
Anders Kaseorg
Puede guardar un byte utilizando argumentos u no desplazados ( ^3↦ *3, tG↦ G) y otro byte con .UgbtH*G]3↦ e.ugNtHG1.
Anders Kaseorg
Una forma alternativa de guardar ese segundo byte es *G]3↦ ShG.
Anders Kaseorg
8

Sesos , 30 bytes

0000000: 286997 2449f0 6f5d10 07f83a 06fffa f941bb ee1f33  (i.$I.o]...:....A...3
0000015: 065333 07dd3e 769c7b                              .S3..>v.{

Desmontado

set numout
add 4
rwd 2
add 64
jmp
    sub 1
    fwd 3
    add 3
    rwd 1
    add 1
    jmp
        sub 1
        jmp
            fwd 1
            jmp
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                rwd 1
                jmp
                    sub 1
                    fwd 3
                    add 1
                    rwd 3
                jnz
                fwd 3
                jmp
                    sub 1
                    rwd 2
                    add 1
                    rwd 1
                    add 1
                    fwd 3
                jnz
                rwd 1
                sub 1
            jnz
            rwd 1
            jmp
                sub 1
            jnz
            add 1
            rwd 1
            sub 1
        jnz
        fwd 1
        jmp
            sub 1
            rwd 1
            add 3
            fwd 1
        jnz
        rwd 2
    jnz
    rwd 1
jnz
fwd 2
put

O en notación Brainfuck:

++++<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[->>>+++<+[-[>[[->+<]<[->>>+<<<]>>>[-<<+<+>>>]<-]<[-]+<-]>[-<+++>]<<]<]>>.

Pruebas

Para calcular u (3, n , T (3, n , ... u (3, n , m ) ...)) con k llamadas anidadas para u , reemplace las tres primeras addinstrucciones add 4, add 64, add 3con add m, add k, add n, respectivamente. Debido a que Sesos no puede construir números más rápido que en tiempo lineal, está prácticamente limitado a valores pequeños como u (3, 2, 2) = 27, u (3, 5, 1) = 243 yu (3, 1 , u (3, 1, ... u (3, 1, m ) ...)) = 3.

Anders Kaseorg
fuente
Puede reemplazar [-]con ,ya que EOF es 0.
mbomb007
6

JavaScript (ES7), 63 bytes

u=(n,m)=>n>1&m>1?u(u(n-1,m),m-1):3**n
g=n=>n?u(3,g(n-1)):4
g(64)
Neil
fuente
@AndersKaseorg Ugh, en ese caso también podría revertir ese cambio.
Neil
Esto provoca un desbordamiento de la pila, es posible que deba volver a verificar su patrón de recursión.
NodeNodeNode
Esto no es simple ES7. Este es ES7 ilimitado (una variante imaginaria de ES7 pero con bignum, capaz de formar un oráculo infinitamente, y está usando decimal con / # xE ^ como abreviatura).
user75200
5

Brachylog , 57 bytes

4:64:1iw
:3{[1:N],3:N^.|t1,3.|hM:1-X,?t:1-:Mr:2&:Xr:2&.}.

No espera entrada ni salida y escribe el resultado en STDOUT. Esto producirá un desbordamiento de pila en un punto.

Para comprobar que esto funciona para valores pequeños (p u(3,3,2). Ej. ), Puede reemplazar el 4con el valor de my 64con 1.

Explicación

Esto es básicamente una implementación directa de la forma explicada de calcular el número.

  • Predicado principal:

    4:64:1i                    Call Predicate 1 64 times with 4 as initial input (the second
                           call takes the output of the first as input, etc. 64 times).
       w                   Write the final output to STDOUT

  • Predicado 1:

    :3{...}.                   Call predicate 2 with input [Input, 3]. Its output is the 
                           output of predicate 1.

  • Predicado 2:

    [1:N],                     M = 1
      3:N^.                Output = 3^N
|                          Or
t1,                        N = 1
   3.                      Output = 3
|                          Or
hM:1-X,                    X is M - 1
       ?t:1-:Mr:2&         Unify an implicit variable with u(3,N-1,M)
                  :Xr:2&.  Unify Output with u(3,u(3,N-1,M),X)
Fatalizar
fuente
5

Caramelo , 38 bytes

(64 ((f->(f,1)),(n f->(3 (n f))),3) 4)

Este es el azúcar sintáctico para la expresión 64 del cálculo lambda (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, donde todos los números se representan como Iglesia números .

Anders Kaseorg
fuente
(n f->3 (n f))no debería leer n-1?
Leaky Nun
@LeakyNun No. (n f->3 (n f))es una función para multiplicar por tres en los números de la Iglesia .
Anders Kaseorg
2
Este desafío parece excesivamente simple en el cálculo lambda. ¿Por qué?
gato
3

Prólogo (SWIPL), 129/137 bytes

g(1,R):-u(3,4,R).
g(L,R):-M is L-1,g(M,P),u(3,P,R).
u(N,1,R):-R is 3**N.
u(1,_,3).
u(N,M,R):-K is N-1,L is M-1,u(K,M,Y),u(Y,L,R).

Para generar el número de Graham, busque g(64,G).(si se van a contar los 8 bytes de esta consulta, la longitud es 137 bytes):

?- g(64, G).
ERROR: Out of local stack

Pero como se puede esperar, esto se agota.

Prueba

?- u(3, 2, X).
X = 7625597484987

El retroceso hace que se quede sin pila:

?- u(3, 2, X).
X = 7625597484987 ;
ERROR: Out of local stack

Sin golf

La versión sin golf agrega la notación general de flecha hacia arriba, no solo para 3, y utiliza cortes y comprobaciones para evitar retroceder y situaciones indefinidas.

% up-arrow notation
u(X, 1, _M, X) :- !.
u(X, N, 1, R) :-
    R is X**N, !.
u(X, N, M, R) :-
    N > 1,
    M > 1,
    N1 is N - 1,
    M1 is M - 1,
    u(X, N1, M, R1),
    u(X, R1, M1, R).

% graham's number
g(1,R) :- u(3, 3, 4, R), !.
g(L,R) :-
    L > 1,
    L1 is L - 1,
    g(L1,G1),
    u(3, G1, R).
SQB
fuente
¿Cómo logró hacerlo sin tener el número 64en ninguna parte de su código?
Leaky Nun
@LeakyNun edité para aclarar; ¿mejor?
SQB
Bueno, entonces agrégalo a tu código y a tu cuenta de bytes.
Leaky Nun
3

C, 161 bytes

u(int a, int b){if(a==1)return 3;if(b==1)return pow(3,a);return u(u(a-1,b),b-1);}
g(int a){if(a==1)return u(3,4);return u(3,g(a-1));}
main(){printf("%d",g(64));}

EDITAR: ahorró 11 bytes eliminando pestañas y nuevas líneas. EDITAR: thx auhmann guardó otro byte y arregló mi programa

la flecha de perforación
fuente
1
Podrías eliminarlo g(int a){if(a==1)return u(3,4);return g(a-1);}ya que no se está utilizando en absoluto ... ¿O estás olvidando algo?
auhmaan
@auhmaan, perdón, usé ese número para probar y olvidé cambiarlo de nuevo. ¡¡Gracias!!
thepiercingarrow
Tu return g(a-1)deberías ser return u(3,g(a-1)).
Anders Kaseorg
1
No sé si debería dar una respuesta adecuada o simplemente comentar sobre esto, pero puede obtener esta solución a 114 bytes con bastante facilidad al darse cuenta: se pueden omitir nuevas líneas entre funciones. La omisión de los tipos para todos los argumentos los establece por defecto en int (piense en K&R). Si declaraciones como estas se pueden escribir con operaciones ternarias anidadas. Código:u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}g(a){return a<2?u(3,4):u(3,g(a-1));}main(){printf("%d",g(64));}
algmyr
@algmyr wow increíble! deberías publicar tu propia respuesta XD.
thepiercingarrow
2

Mathematica, 59 bytes

n_ ±1:=3^n
1 ±m_:=3
n_ ±m_:=((n-1)±m)±(m-1)
Nest[3±#&,4,64]

Utiliza un operador infijo indefinido ±que requiere solo 1 byte cuando está codificado en ISO 8859-1. Vea la publicación de @ Martin para más información. Las funciones de Mathematica admiten la coincidencia de patrones para sus argumentos, de modo que los dos casos base se pueden definir por separado.

millas
fuente
1
¿Desde cuándo Mathematica usó ISO 8859-1?
Leaky Nun
n_ ±m_:=Nest[#±(m-1)&,3,n]
Leaky Nun
2

C, 114 109 bytes

Basado en la respuesta de @thepiercingarrow ( enlace ), bajé bastante la respuesta. La mayoría de los ahorros se deben al abuso del tipeo predeterminado de los argumentos al realizar funciones de estilo K&R y al reemplazo de declaraciones if con operadores ternarios. Se agregaron nuevas líneas opcionales entre funciones para facilitar la lectura.

Mejorado a 109 gracias a @LeakyNun.

u(a,b){return a<2?3:b<2?pow(3,a):u(u(a-1,b),b-1);}
g(a){return u(3,a<2?4:g(a-1));}
main(){printf("%d",g(64));}
algmyr
fuente
g(a){return u(3,a<2?4:g(a-1));}
Leaky Nun
@LeakyNun Esa es una muy buena. Gracias.
algmyr
1

Python, 85 bytes

v=lambda n,m:n*m and v(v(n-1,m)-1,m-1)or 3**-~n
g=lambda n=63:v(2,n and g(n-1)-1or 3)

La vfunción define la misma función que la encontrada en la respuesta de Dennis : v(n,m) = u(3,n+1,m+1). La gfunción es una versión cero indexada de la iteración tradicional: g(0) = v(2,3), g(n) = v(2,g(n-1)). Por lo tanto, g(63)es el número de Graham. Al establecer el valor predeterminado del nparámetro de la gfunción en 63, la salida requerida se puede obtener llamando g()(sin parámetros), cumpliendo así con nuestros requisitos para un envío de función que no requiere entrada.

Verifique los casos de prueba v(2,1) = u(3,3,2)y en v(4,0) = u(3,5,1)línea: Python 2 , Python 3

Mego
fuente
1
Es un poco difícil de verificar, pero su función gparece estar apagada. ¿No debería v(2,n-1)ser g(n-1)o algo similar?
Dennis
@Dennis Buena captura. Lo arreglaré
Mego
En realidad, el desplazamiento entre uy vsignifica que debería ser g(n-1)-1.
Anders Kaseorg
@AndersKaseorg No debería hacer programación mientras tengo sueño. Tengo que volver a aprender esto cada pocos días.
Mego
@AndersKaseorg En el futuro, no edite los envíos de otras personas, incluso si se trata de corregir un error en una mejora / corrección de errores que sugirió.
Mego
1

Dyalog APL, 41 bytes

u←{1=⍺:3⋄1=⍵:3*⍺⋄(⍵∇⍨⍺-1)∇⍵-1}
3u 3u⍣64⊣4

Caso de prueba:

      3u 2
7625597484987
lstefano
fuente
Debería poder convertir 1=⍺:3⋄1=⍵:3*⍺a just 1=⍵:3*⍺( 3=3*1)
Zacharý
1

Ruby, 64 bytes

Préstamo del algoritmo teórico para calcular el número de Graham .

def f(a,b=3)b<2?3:a<1?3*b:f(a-1,f(a,b-1))end;a=4;64.times{a=f a};p a

En pocas palabras, f a = u(3,3,a)y se aplica esto 64 veces.

Simplemente hermoso arte
fuente
Una buena explicación de por qué y cómo funciona este código sería bueno.
Manish Kundu
Es una aplicación directa de la definición del número de Graham.
Simplemente hermoso arte
0

J, 107 bytes

u=:4 :0
if.y=1 do.3^x
elseif.x=1 do.3
elseif.1 do.x:(y u~<:x)u<:y
end.
)
(g=:(3 u 4[[)`(3 u$:@<:)@.(1&<))64

Estoy trabajando para convertirme uen una agenda, pero por ahora será suficiente.

Conor O'Brien
fuente
Algo como u=:3^[`[:(3$:])/[#<:@]@.*@](no probado)
Leaky Nun
0

F #, 111108 bytes

Editar

Esto está utilizando la función a continuación para calcular el número de Graham

let rec u=function|b,1->int<|3I**b|1,c->3|b,c->u(u(b-1,c),c-1)
and g=function|1->u(3.,4.)|a->u(3.,g (a-1))
g 63

Aquí está mi respuesta anterior que, bueno, no:

Muy claro. Solo una definición de la ufunción.

let rec u=function|a,b,1->a**b|a,1.,c->a|a,b,c->u(a,u(a,b-1.,c),c-1)

Uso:

u(3.,3.,2)
val it : float = 7.625597485e+12

Si supuse 3 como el valor de a, podría reducirlo a 60:

let rec u=function|b,1->3.**b|1.,c->3.|b,c->u(u(b-1.,c),c-1)

Uso:

u(3.,2)
val it : float = 7.625597485e+12
asibahi
fuente
El desafío es escribir el número de Graham, no u. Por supuesto, puede incluir cualquier función intermedia que necesite, como ucon o sin su primer argumento fijado en 3.
Anders Kaseorg
@AndersKaseorg lo editó. Gracias. Mi comentario anterior parece haber desaparecido.
asibahi
0

R, 154 142 128 126 118 bytes

u=function(n,b)return(if(n&!b)1 else if(n)u(n-1,u(n,b-1))else 3*b)
g=function(x)return(u(if(x-1)g(x-1)else 4,3))
g(64)

Utilicé la definición de Wikipedia de esta función recursiva porque, por alguna extraña razón, la sugerida no funcionó ... o simplemente apestaba en R golf.

UPD: afeitado 12 + 14 = 26 bytes gracias a un consejo de Leaky Nun . La versión anterior utilizaba el voluminoso y menos eficiente.

u=function(n,b)if(n==0)return(3*b)else if(n>0&b==0)return(1)else return(u(n-1,u(n,b-1)))
g=function(x)if(x==1)return(u(4,3))else return(u(g(x-1),3))

UPD: afeitado 2 + 6 + 2 bytes más (nuevamente, felicitaciones a Leaky Nun ) debido a un ingenioso reemplazo con "if (x)" en lugar de "if (x == 0)" porque x <0 nunca se introduce en la función ... ¿verdad?

Andreï Kostyrka
fuente
@LeakyNun Gracias, actualicé la respuesta con reconocimiento.
Andreï Kostyrka
Solo un segundo ... Hoy es mi primer día de golf de código, ¡hay mucho que aprender!
Andreï Kostyrka
Estás invitado a unirte a nuestro chat .
Leaky Nun
Más golf, por favor vea la mejora.
Andreï Kostyrka
Ta-dam, hecho, cambió la función uen la misma tecla que tu gy guardó 6 bytes más, ¡increíble!
Andreï Kostyrka
0

PHP, 114 bytes

ignorar los saltos de línea; son solo para legibilidad.

function u($n,$m){return$m>1&$n>1?u(u($n-1,$m),$m-1):3**$n;}
function g($x){return u(3,$x>1?g($x-1):4);}
echo g(63);

Es posible integrar el segundo caso en el primero: para n=1, 3^nes igual3 .
Esto ahorrará algunos bytes en, por lo que puedo ver, todas las respuestas existentes; guardado dos bytes en mi

versión anterior, 62 + 43 + 11 = 116 bytes

function u($n,$m){return$m>1?$n>1?u(u($n-1,$m),$m-1):3:3**$n;}

La asociatividad izquierda de PHP del ternario requiere paréntesis ... o un orden específico de pruebas.
Esto ahorró dos bytes en la expresión entre paréntesis.

Probablemente hay un enfoque iterativo, que puede permitir más golf ...
pero no puedo tomarme el tiempo ahora.

Titus
fuente
Ojalá conociera a Sesos o tuviera tiempo de aprenderlo y traducirlo ahora mismo
Titus
@Leaky Nun: lo dividí en solo bucles y adición. ¿Hay alguna forma en Sesos de agregar el valor de una celda a otra?
Titus
@AndersKaseorg: Probablemente tengas razón ... Tengo ampollas en los globos oculares al mirar ese algoritmo. Lo miraré de nuevo pronto.
Tito