Liczba Grahama Gjest zdefiniowana w następujący sposób:

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)

Masz to za u(3,3,2)=7625597484987zadanie sprawdzić swój kod.

Twoim zadaniem jest napisanie programu / funkcji, która wyświetli wartość Gdeterministycznie, biorąc pod uwagę wystarczającą liczbę całkowitą i wystarczająco dużo czasu.

Bibliografia

• Numer Grahama
• Notacja Knutha skierowana w górę
• Łańcuchowa notacja strzała Conwaya

Tabela liderów

var QUESTION_ID=83873,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Binarny rachunek lambda , 114 bitów = 14,25 bajtów

Hexdump:

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

Dwójkowy:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Wyjaśnienie

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

Jest to (λ 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, gdzie wszystkie liczby są reprezentowane jako cyfry kościelne. Liczby kościelne są standardową reprezentacją liczb naturalnych w rachunku lambda i dobrze nadają się do tego problemu, ponieważ liczbę kościelną definiuje się przez iterację funkcji: n g jest n- tym iteratem funkcji g .

Na przykład, jeśli g jest funkcją λ n . λ f . 3 ( n f ), który mnoży 3 przez liczbę kościelną, a następnie λ n . n g 1 to funkcja, która przenosi 3 do potęgi liczby Kościoła. Powtórzenie tej operacji m razy daje

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

(Używamy mnożenia u (-, -, 0) zamiast potęgowania u (-, -, 1) jako podstawowego przypadku, ponieważ odejmowanie 1 od liczby kościelnej jest nieprzyjemne .)

Zamień n = 3:

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

Iterowanie tej operacji 64 razy, zaczynając od m = 4, daje

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

Aby zoptymalizować to wyrażenie, podstaw 64 = 4 ^ 3 = 3 4:

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

Pamiętaj 4 = succ 3 = λ f . λ z . f (3 f z ) jako argument 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 .

Na koniec pamiętaj 3 = λ f . λ z . f ( f ( f z )) jako argument 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 .

Haskell, 41 bajtów

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

Wyjaśnienie:

(`i`1)f n= i f 1 noblicza niterat funkcji frozpoczynający się od 1. W szczególności (`i`1)(*3)n= 3 ^ n , a iteracja tej konstrukcji m razy daje i(`i`1)(*3)m n= u (3, n , m ). Możemy przepisać to jako (($n).i(`i`1)(*3))m= u (3, n , m ) i iterować tę konstrukcję k razy, aby uzyskać i(($3).i(`i`1)(*3))4 k= g _ k .

Haskell, 43 bajty

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

Istnieje lepszy sposób na odwrócenie w glinii.

46 bajtów:

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

48 bajtów:

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

Zapisuję definicje.

Podstawowe przypadki są nieco czystsze, a ich kopia zapasowa wynosi 0, ale nie oszczędza bajtów. Być może ułatwi to napisanie alternatywnej definicji.

n%0=3*n
0%m=1
n%m=(n-1)%m%(m-1)
z=iterate(3%)2!!1

Pyth, 25 bajtów

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

Pierwsza część M?H.UgbtH*G]3^3Gokreśla metodę g(G,H) = u(3,G,H+1).

Aby przetestować pierwszą część należy sprawdzić, czy 7625597484987=u(3,3,2)=g(3,1): g3 1.

Druga część ug3tG64 4zaczyna się od, r0 = 4a następnie oblicza rn = u(3,3,r(n-1)) = g(3,r(n-1))64 razy, wyprowadzając końcową wartość ( rjest wybierana zamiast, gaby uniknąć zamieszania).

Aby przetestować tę część, zacznij od r0=2a następnie obliczyć r1: ug3tG1 2.

Sesos , 30 bajtów

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

Zdemontowane

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

Lub w notacji Brainfuck:

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

Testowanie

Aby obliczyć u (3, n , u (3, n , ... U (3, n , m ), ...)) z k zagnieżdżone wywołaniami u wymienić trzech pierwszych addinstrukcji add 4, add 64, add 3o add m, add k, add nodpowiednio. Ponieważ Sesos nie może budować liczb szybciej niż w czasie liniowym, praktycznie jesteś ograniczony do małych wartości, takich jak u (3, 2, 2) = 27, u (3, 5, 1) = 243 iu (3, 1 , u (3, 1,… u (3, 1, m )…)) = 3.

JavaScript (ES7), 63 bajty

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)

Brachylog , 57 bajtów

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

Nie oczekuje danych wejściowych ani wyjściowych i zapisuje wynik do STDOUT. Spowoduje to przepełnienie stosu w jednym punkcie.

Aby sprawdzić, czy działa to dla małych wartości (na przykład u(3,3,2)) można zastąpić 4o wartości mi 64z 1.

Wyjaśnienie

Jest to w zasadzie prosta implementacja wyjaśnionego sposobu obliczania liczby.

• Główny predykat:

  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
  

• Predykat 1:

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

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

Karmel , 38 bajtów

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

To cukier syntaktyczny dla wyrażenia rachunku lambda 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, gdzie wszystkie liczby są reprezentowane jako kościół cyfry .

Prolog (SWIPL), 129/137 bajtów

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

Aby wyprowadzić liczbę Grahama, zapytaj o g(64,G).(jeśli należy policzyć 8 bajtów tego zapytania, długość wynosi 137 bajtów):

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

Ale jak można się spodziewać, kończy się to na stosie.

Test

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

Cofanie powoduje, że zaczyna brakować stosu:

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

Nie golfił

Wersja bez golfa dodaje ogólną notację ze strzałką w górę, nie tylko dla 3, i wykorzystuje cięcia i kontrole, aby uniknąć cofania się i nieokreślonych sytuacji.

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

C, 161 bajtów

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

EDYCJA: zapisano 11 bajtów, usuwając tabulatory i znaki nowej linii. EDYCJA: thx auhmann zapisał kolejny bajt i naprawił mój program

Mathematica, 59 bajtów

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

Wykorzystuje niezdefiniowany operator poprawki, ±który wymaga tylko 1 bajtu, gdy jest zakodowany w ISO 8859-1. Zobacz post @ Martina, aby uzyskać więcej informacji. Funkcje matematyczne obsługują dopasowanie wzorca dla ich argumentów, dzięki czemu dwa przypadki podstawowe można zdefiniować osobno.

C, 114 109 bajtów

Opierając się na odpowiedzi @thepiercingarrow ( link ), grałem trochę w golfa. Większość oszczędności wynika z nadużywania domyślnego wpisywania argumentów podczas wykonywania funkcji w stylu K&R i zamiany instrukcji if na trójskładnikowe operatory. Dodano opcjonalne znaki nowej funkcji między funkcjami dla czytelności.

Poprawiono do 109 dzięki @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));}

Python, 85 bajtów

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)

vFunkcja definiuje taką samą funkcję jak ten znaleziony w odpowiedzi Dennisa : v(n,m) = u(3,n+1,m+1). gFunkcja jest zero-indeksowane wersja tradycyjnego iteracji: g(0) = v(2,3), g(n) = v(2,g(n-1)). Zatem g(63)jest liczbą Grahama. Ustawiając domyślną wartość nparametru gfunkcji na 63, można uzyskać wymaganą moc wyjściową przez wywołanie g()(bez parametrów), spełniając w ten sposób nasze wymagania dotyczące przesyłania funkcji, która nie wymaga wprowadzania danych.

Sprawdź v(2,1) = u(3,3,2)i v(4,0) = u(3,5,1)przetestuj przypadki online: Python 2 , Python 3

Dyalog APL, 41 bajtów

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

Przypadek testowy:

      3u 2
7625597484987

Rubinowy, 64 bajty

Pożyczki z algorytmu teoretycznego do obliczenia liczby Grahama .

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

Mówiąc wprost, f a = u(3,3,a)dotyczy to 64 razy.

J, 107 bajtów

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

Pracuję nad konwersją udo programu, ale na razie się uda.

F #, 111 108 bajtów

Edytować

Wykorzystuje to poniższą funkcję do obliczenia liczby Grahama

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

Oto moja poprzednia odpowiedź, która, no cóż, nie:

Całkiem proste. Po prostu definicja ufunkcji.

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)

Stosowanie:

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

Gdybym przyjął 3 jako wartość dla a, mógłbym ją obniżyć do 60:

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

Stosowanie:

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

R, 154 142 128 126 126 118 bajtów

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)

Użyłem definicji Wikipedii tej funkcji rekurencyjnej, ponieważ z jakiegoś dziwnego powodu sugerowana nie działała ... lub po prostu ssę golfa R.

UPD: wygolono 12 + 14 = 26 bajtów dzięki końcówce od Leaky Nun . Poprzednia wersja wykorzystywała nieporęczne i mniej wydajne

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: wygolono o 2 + 6 + 2 dodatkowe bajty (ponownie, uznanie dla Dziurawej Zakonnicy ) dzięki pomysłowej zamianie na „if (x)” zamiast „if (x == 0)”, ponieważ x <0 nigdy nie jest wprowadzane do funkcja ... prawda?

PHP, 114 bajtów

zignoruj ​​podział linii; służą wyłącznie do odczytu.

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

Możliwe jest zintegrowanie drugiego przypadku z pierwszym: dla n=1, 3^nrówna się 3.
Pozwoli to zaoszczędzić kilka bajtów - o ile widzę - na wszystkich istniejących odpowiedziach; zapisałem dwa bajty na moim

poprzednia wersja, 62 + 43 + 11 = 116 bajtów

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

Lewe skojarzenie trójskładnika PHP wymaga nawiasów ... lub określonej kolejności testów.
Pozwoliło to zaoszczędzić dwa bajty wyrażenia w nawiasach.

Prawdopodobnie istnieje podejście iteracyjne, które może pozwolić na dalszą grę w golfa ...
ale nie mogę teraz na to pozwolić .