Teoricamente, o número de Graham

44

O número de Graham Gé definido desta maneira:

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)

Você tem que u(3,3,2)=7625597484987verificar seu código.

Sua tarefa é escrever um programa / função que produzirá o valor de Gdeterministicamente, considerando tamanho inteiro suficiente e tempo suficiente.

Referências

Entre os melhores

Mostrar snippet de código

code-golf number-theory Freira Furada
fonte
2
Relacionado .
Freira vazada
7
A aleatoriedade é permitida? Se eu apenas emitir valores aleatórios, eventualmente o número de Graham deve ser produzido.
miles
15
@miles Por que diabos já não é uma brecha padrão? Esclarecido.
Leaky Nun
18
Aviso: u (3, 3, 2) = u (3, 2, 3) = 7625597484987, portanto, você também desejará testar outros valores como u (3, 5, 1) = 243 para garantir que você tenha a ordem dos argumentos está correta.
Anders Kaseorg 27/06
2
Número de Graham?
Beta Decay

Respostas:

48

Cálculo lambda binário , 114 bits = 14,25 bytes

Hexdump:

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

Binário:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Explicação

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)))

Isto é (λ 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, onde todos os números são representados como números da Igreja. Os números da igreja são a representação padrão do cálculo lambda dos números naturais e são adequados para esse problema porque um número da igreja é definido pela iteração da função: n g é a n- ésima iteração da função g .

Por exemplo, se g é a função λ n . λ f . 3 ( n f ) que multiplica 3 por um número da Igreja, então λ n . n g 1 é a função que leva 3 ao poder de um numeral da Igreja. Iterar esta operação m vezes fornece

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

(Usamos a multiplicação u (-, -, 0) em vez da exponenciação u (-, -, 1) como o caso base, porque subtrair 1 de um numeral da Igreja é desagradável .)

Substituto n = 3:

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

Iterando essa operação 64 vezes, iniciando em m = 4, fornece

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

Para otimizar essa expressão, substitua 64 = 4 ^ 3 = 3 4:

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

Lembre-se de 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 )) = L .

Finalmente, lembre-se de 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 = L .

Anders Kaseorg
fonte
Onde alguém poderia encontrar um intérprete para esse idioma?
Dennis
4
O @Dennis tromp.github.io/cl/cl.html possui alguns deles.
Anders Kaseorg
1
Isso é demais . isso merece uma recompensa considerável
cat
1
14.25 bytesparece estar atrapalhando a classificação. Ele é analisado como 25 bytese, portanto, você é colocado como segundo.
Dan
1
@ Dan Corrigi o snippet do quadro de líderes, eu acho.
Anders Kaseorg
40

Haskell, 41 bytes

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

Explicação:

(`i`1)f n= i f 1 ncalcula a niteração da função finiciando em 1. Em particular, (`i`1)(*3)n= 3 ^ n , e a iteração dessa construção m vezes fornece i(`i`1)(*3)m n= u (3, n , m ). Podemos reescrever que quanto (($n).i(`i`1)(*3))m= u (3, n , m ), e repita essa construção k vezes para obter i(($3).i(`i`1)(*3))4 k= g _ k .

Anders Kaseorg
fonte
16

Haskell, 43 bytes

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

Existe uma maneira melhor de ginline.

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

Apenas anotando as definições.

Os casos base são um pouco mais limpos, com backup de 0, embora não salvem bytes. Talvez seja mais fácil escrever uma definição alternativa.

n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1
xnor
fonte
Você pode usar outra função que tenha precedência menor que +para remover os parênteses entre eles m-1?
Leaky Nun
Conto 44 bytes, e o que aconteceu com 4 e 64?
Freira vazada
Ops, copiei no meu teste de parâmetro menor. Acho que não posso alterar a precedência do operador porque estou definindo uma nova função e essas têm uma precedência padrão. Não consigo substituir uma função existente.
xnor
Quer dizer, eu contar 44 bytes depois de mudá-lo de volta para 64.
Leaky Nun
Eu acho que você quer dizer (`g`3), não (3`g`).
Anders Kaseorg
10

Pitão, 25 bytes

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

A primeira parte M?H.UgbtH*G]3^3Gdefine um método g(G,H) = u(3,G,H+1).

Para testar a primeira parte, verifique se 7625597484987=u(3,3,2)=g(3,1): g3 1.

A segunda parte ug3tG64 4começa r0 = 4e depois calcula rn = u(3,3,r(n-1)) = g(3,r(n-1))64 vezes, produzindo o valor final ( ré escolhido em vez de gevitar confusão).

Para testar esta parte, comece a partir r0=2e depois calcular r1: ug3tG1 2.

Freira Furada
fonte
Se g (G, H) = u (3, G, H + 1), você deve ter r (n) = u (3, 3, r (n - 1)) = g (3, r (n - 1 ) - 1), não g (3, r (n - 1)). Eu acho que o seu código é certo, mas a sua explicação está faltando o - 1.
Anders Kaseorg
Você pode salvar um byte usando u argumentos não compensados ​​( ^3↦ *3, tG↦ G) e outro byte com .UgbtH*G]3↦ e.ugNtHG1.
Anders Kaseorg
Uma maneira alternativa de salvar esse segundo byte é *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

Ou na notação Brainfuck:

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

Testando

Para calcular u (3, n , L (3, n , ... u (3, n , m ) ...)) com k aninhados chamadas para u , substituir as três primeiras addinstruções add 4, add 64, add 3com add m, add k, add n, respectivamente. Como o Sesos não pode construir números mais rapidamente do que no tempo linear, você está praticamente limitado a pequenos valores como u (3, 2, 2) = 27, u (3, 5, 1) = 243 e u (3, 1 , u (3, 1,… u (3, 1, m )…)) = 3.

Anders Kaseorg
fonte
Você pode substituir [-]por ,EOF 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
fonte
@AndersKaseorg Ugh, nesse caso, é melhor reverter essa alteração.
Neil
Isso causa um estouro de pilha, pode ser necessário verificar novamente seu padrão de recursão.
NodeNodeNode 19/10
Isso não é simples ES7. Esse é o ES7 ilimitado (uma variante imaginária do ES7, mas com bignum, capaz de oracle infinitamente, e está usando decimal com / # xE ^ como abreviação).
precisa saber é o seguinte
5

Braquilog , 57 bytes

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

Não espera entrada nem saída e grava o resultado em STDOUT. Isso produzirá um estouro de pilha em um ponto.

Para verificar se isso funciona com valores pequenos (por exemplo u(3,3,2)), você pode substituir o 4com o valor de me 64com 1.

Explicação

Essa é basicamente uma implementação direta da maneira explicada de calcular o 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
fonte
5

Caramelo , 38 bytes

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

Este é um açúcar sintático para a expressão de cálculo lambda 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, onde todos os números são representados como Igreja numerais .

Anders Kaseorg
fonte
(n f->3 (n f))não deveria ler n-1?
Freira vazada
@LeakyNun No. (n f->3 (n f))é uma função para multiplicação de três em numerais da Igreja .
Anders Kaseorg
2
Esse desafio parece excessivamente simples no cálculo lambda. Por quê?
cat
3

Prolog (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 gerar o número de Graham, consulte g(64,G).(se os 8 bytes dessa consulta devem ser contados, o comprimento é de 137 bytes):

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

Mas, como é de se esperar, isso fica sem pilha.

Teste

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

Voltar atrás faz com que fique sem pilha:

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

Ungolfed

A versão ungolfed adiciona a notação geral da seta para cima, não apenas para 3, e usa cortes e verificações para evitar retroceder e situações 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
fonte
Como você conseguiu fazer isso sem ter o número 64em nenhum lugar do seu código?
Leaky Nun
@LeakyNun eu editei para esclarecer; Melhor?
SQB
Bem, adicione-o ao seu código e também à sua contagem 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));}

EDIT: salvou 11 bytes removendo guias e novas linhas. EDIT: thx auhmann salvou outro byte e corrigiu meu programa

thepiercingarrow
fonte
1
Você pode remover, g(int a){if(a==1)return u(3,4);return g(a-1);}já que não está sendo usado ... Ou você está esquecendo alguma coisa?
31516 auhmaan
@auhmaan oops desculpe, eu usei esse número para testar e esqueci de mudar de volta. Obrigado!!
thepiercingarrow
Você return g(a-1)deveria ser return u(3,g(a-1)).
Anders Kaseorg
1
Não sei se devo dar uma resposta adequada ou apenas comentar sobre isso, mas você pode obter essa solução com até 114 bytes facilmente, percebendo: Novas linhas entre funções podem ser omitidas. A omissão de tipos para todos os argumentos os padroniza para int (pense em K&R). Se declarações como essas podem ser escritas com operações ternárias aninhadas. 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 amazing! você deve postar sua própria resposta XD.
Thepiercingarrow
2

Mathematica, 59 bytes

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

Usa um operador infixo indefinido ±que requer apenas 1 byte quando codificado na ISO 8859-1. Veja a publicação de @ Martin para mais informações. As funções do Mathematica suportam a correspondência de padrões para seus argumentos, de modo que os dois casos base possam ser definidos separadamente.

milhas
fonte
1
Desde quando o Mathematica usa a ISO 8859-1?
Freira vazada
n_ ±m_:=Nest[#±(m-1)&,3,n]
Freira vazada
2

C, 114 109 bytes

Com base na resposta de @thepiercingarrow ( link ), reduzi bastante a resposta. A maioria das economias se deve ao abuso da digitação padrão de argumentos ao executar funções no estilo K&R e à substituição de instruções if por operadores ternários. Adicionadas novas linhas opcionais entre funções para facilitar a leitura.

Aprimorado para 109 graças 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
fonte
g(a){return u(3,a<2?4:g(a-1));}
Leaky Nun
@LeakyNun Essa é realmente boa. Obrigado.
14
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)

A vfunção define a mesma função que o encontrado na resposta de Dennis : v(n,m) = u(3,n+1,m+1). A gfunção é uma versão zero indexada da iteração tradicional: g(0) = v(2,3), g(n) = v(2,g(n-1)). Assim, g(63)é o número de Graham. Ao definir o valor padrão do nparâmetro da gfunção como 63, a saída necessária pode ser obtida chamando g()(sem parâmetros), atendendo assim aos nossos requisitos para o envio de uma função que não requer entrada.

Verifique os casos de teste v(2,1) = u(3,3,2)e v(4,0) = u(3,5,1)online: Python 2 , Python 3

Mego
fonte
1
É meio difícil de verificar, mas sua função gparece desativada. Não deveria v(2,n-1)ser g(n-1)ou algo parecido?
Dennis
@ Dennis Boa captura. Eu vou consertar isso.
Mego
Na verdade, o deslocamento entre ue vsignifica que deveria ser g(n-1)-1.
Anders Kaseorg
@AndersKaseorg Não devo programar enquanto estou com sono. Eu tenho que reaprender isso a cada poucos dias.
Mego
@AndersKaseorg No futuro, não edite os envios de outras pessoas, mesmo que seja para corrigir um erro em uma melhoria / correção de bug que você sugeriu.
Mego
1

Dyalog APL, 41 bytes

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

Caso de teste:

      3u 2
7625597484987
lstefano
fonte
Você deve conseguir converter 1=⍺:3⋄1=⍵:3*⍺para just 1=⍵:3*⍺( 3=3*1)
Zacharý
1

Ruby, 64 bytes

Empréstimo do algoritmo teórico para calcular o 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

Simplificando, f a = u(3,3,a)e isso se aplica 64 vezes.

Arte simplesmente bonita
fonte
Uma boa explicação sobre por que e como esse código funciona seria bom.
Manish Kundu
É uma aplicação direta da definição do número de Graham.
Simply Beautiful Art
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

Estou trabalhando na conversão upara uma agenda, mas por enquanto isso serve.

Conor O'Brien
fonte
Algo como u=:3^[`[:(3$:])/[#<:@]@.*@](não testado) #
Leaky Nun
0

F #, 111 108 bytes

Editar

Isso está usando a função abaixo para calcular o 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

Aqui está a minha resposta anterior que, bem, não:

Bem direto. Apenas uma definição da ufunção.

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

Se eu assumisse 3 como o valor de a, poderia reduzi-lo para 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
fonte
O desafio é escrever o número de Graham, não u. É claro que você pode incluir todas as funções intermediárias necessárias, como ucom ou sem o primeiro argumento fixado em 3. #
Anders Kaseorg
O @AndersKaseorg editou isso em. Obrigado. Meu comentário anterior parece ter 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)

Eu usei a definição da Wikipedia dessa função recursiva porque, por alguma razão estranha, a sugerida não funcionou ... ou simplesmente sou péssima no golfe R.

UPD: raspou 12 + 14 = 26 bytes graças a uma dica da Leaky Nun . A versão anterior usava o volumoso e 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: raspou mais 2 + 6 + 2 bytes (novamente, parabéns a Leaky Nun ) devido a uma substituição engenhosa de “if (x)” em vez de “if (x == 0)” porque x <0 nunca é alimentado a função ... certo?

Andreï Kostyrka
fonte
@LeakyNun Obrigado, atualizou a resposta com reconhecimento.
Andreï Kostyrka
Só um segundo ... Hoje é meu primeiro dia de golfe com código, há muito a aprender!
Andreï Kostyrka
Você está convidado a participar do nosso bate-papo .
Leaky Nun
Mais golfe, por favor, veja a melhoria.
Andreï Kostyrka
Ta-dam, feito, mudou a função una mesma tecla que a sua ge salvou mais 6 bytes - incrível!
Andreï Kostyrka
0

PHP, 114 bytes

ignore as quebras de linha; eles são apenas para legibilidade.

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);

É possível integrar o segundo caso no primeiro: for n=1, 3^nigual 3.
Isso economizará alguns bytes em - até onde eu posso ver - todas as respostas existentes; salvou dois bytes no meu

versão 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;}

A associatividade esquerda do ternário do PHP requer parênteses ... ou uma ordem específica de testes.
Isso salvou dois bytes na expressão entre parênteses.

Provavelmente existe uma abordagem iterativa, que pode permitir mais golfe ...
mas não posso reservar um tempo para isso agora.

Titus
fonte
gostaria de saber Sesos ou teve o tempo para aprender e traduzir agora
Titus
Freira @Leaky: eu quebrei para apenas loops e adição. Existe uma maneira no Sesos de adicionar o valor de uma célula para outra?
Titus
@ AndersKaseorg: Você provavelmente está certo ... Eu fiquei com bolhas nos olhos ao olhar para esse algoritmo. Irá olhar para ele novamente em breve.
Titus