Le numéro de Graham Gest défini comme suit:

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)

Vous êtes donné que u(3,3,2)=7625597484987pour vérifier votre code.

Votre tâche consiste à écrire un programme / fonction qui générera la valeur de manière Gdéterministe, avec une taille suffisante pour l’entier et une durée suffisante.

Les références

• Le numéro de Graham
• La notation de Knuth
• Notation de flèche chaînée Conway

Classement

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>

Calcul lambda binaire , 114 bits = 14,25 octets

Hexdump:

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

Binaire:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Explication

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

C'est (λ 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, où tous les nombres sont représentés par des chiffres d'église. Chiffres Eglise sont la représentation standard de calcul lambda des nombres naturels, et ils sont bien adaptés à ce problème , car un certain nombre Eglise est définie par la fonction itération: n g est la n ième itérer de la fonction g .

Par exemple, si g est la fonction λ n . λ f . 3 ( n f ) qui multiplie 3 par un chiffre d'église, puis λ n . n g 1 est la fonction qui prend 3 au pouvoir d'un chiffre d'église. Itérer cette opération m fois donne

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

(Nous utilisons la multiplication u (-, -, 0) plutôt que l'exponentiation u (-, -, 1) comme cas de base, car soustraire 1 à un chiffre d'église est désagréable .)

Suppléant n = 3:

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

Itérant cette opération 64 fois, à partir de m = 4, donne

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

Pour optimiser cette expression, remplacez 64 = 4 ^ 3 = 3 4:

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

Rappelez-vous 4 = succ 3 = λ f . λ z . f (3 f z ) comme 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 .

Enfin, rappelez-vous 3 = λ f . λ z . f ( f ( f z )) en tant qu'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 octets

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

Explication:

(`i`1)f n= i f 1 ncalcule l' nitération de la fonction à fpartir de 1. En particulier, (`i`1)(*3)n= 3 ^ n , et itérer cette construction m fois donne i(`i`1)(*3)m n= u (3, n , m ). Nous pouvons réécrire cela comme (($n).i(`i`1)(*3))m= u (3, n , m ) et itérer cette construction k fois pour obtenir i(($3).i(`i`1)(*3))4 k= g _ k .

Haskell, 43 octets

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

Il y a une meilleure façon de retourner en gligne.

46 octets:

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

48 octets:

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

Il suffit d'écrire les définitions.

Les cas de base sont un peu plus propres, ils sont sauvegardés à 0, bien que cela ne sauvegarde aucun octet. Peut-être que cela facilitera l’écriture d’une autre définition.

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

Pyth, 25 octets

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

La première partie M?H.UgbtH*G]3^3Gdéfinit une méthode g(G,H) = u(3,G,H+1).

Pour tester la première partie, vérifier que 7625597484987=u(3,3,2)=g(3,1): g3 1.

La deuxième partie ug3tG64 4commence r0 = 4et calcule ensuite rn = u(3,3,r(n-1)) = g(3,r(n-1))64 fois, en fournissant la valeur finale (à rchoisir au lieu de gpour éviter toute confusion).

Pour tester cette partie, recommencez à partir r0=2, puis calculer r1: ug3tG1 2.

Sesos , 30 octets

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

Démonté

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 en notation Brainfuck:

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

Essai

Pour calculer u (3, n , u (3, n , ... u (3, n , m ) ...)) avec k appels imbriqués pour u , remplacer les trois premières addinstructions add 4, add 64, add 3avec add m, add k, add n, respectivement. Comme Sesos ne peut pas construire de nombres plus rapidement qu'en temps linéaire, vous êtes pratiquement limité à de petites valeurs telles que u (3, 2, 2) = 27, u (3, 5, 1) = 243 et u (3, 1 , u (3, 1,… u (3, 1, m )…)) = 3.

JavaScript (ES7), 63 octets

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 octets

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

N'attend ni entrée ni sortie et écrit le résultat dans STDOUT. Cela produira un débordement de pile à un moment donné.

Pour vérifier que cela fonctionne pour de petites valeurs (par exemple u(3,3,2)), vous pouvez remplacer le 4avec la valeur de met 64par 1.

Explication

Il s’agit d’une simple implémentation de la manière expliquée de calculer le nombre.

• Prédicat 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
  

• Prédicat 1:

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

• Prédicat 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)
  

Caramel , 38 octets

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

C'est le sucre syntaxique pour l'expression du lambda calcul 64 (λ m . M (λ f . Λ n . N f 1) (λ n . Λ f . 3 ( n f )) 3) 4, où tous les nombres sont représentés par Church chiffres .

Prolog (SWIPL), 129/137 octets

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

Pour sortir le numéro de Graham, interrogez pour g(64,G).(si les 8 octets de cette requête doivent être comptés, la longueur est de 137 octets):

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

Mais comme on peut s'y attendre, cela manque de pile.

Tester

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

Le retour en arrière provoque son épuisement:

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

Ungolfed

La version non golfée ajoute la notation générale de la flèche vers le haut, pas seulement pour 3, et utilise des coupes et des contrôles pour éviter les retours en arrière et les situations non définies.

% 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 octets

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: enregistré 11 octets en supprimant les onglets et les nouvelles lignes. EDIT: thx auhmann a sauvegardé un autre octet et corrigé mon programme

Mathematica, 59 octets

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

Utilise un opérateur infixe non défini ±qui ne requiert qu'un octet lorsqu'il est codé selon ISO 8859-1. Voir le post de @ Martin pour plus d'informations. Les fonctions Mathematica prennent en charge la correspondance des modèles pour leurs arguments, de sorte que les deux cas de base peuvent être définis séparément.

C, 114 109 octets

Sur la base de la réponse de @thepiercingarrow ( lien ), j'ai joué au golf la réponse un peu. La plupart des économies sont dues à l'abus de typage par défaut des arguments lors de l'exécution de fonctions de style K & R et au remplacement des instructions if par des opérateurs ternaires. Ajout de sauts de ligne optionnels entre les fonctions pour plus de lisibilité.

Amélioré à 109 grâce à @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 octets

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 vfonction définit la même fonction que celle trouvée dans la réponse de Dennis : v(n,m) = u(3,n+1,m+1). La gfonction est une version zéro indexée de l'itération traditionnelle: g(0) = v(2,3), g(n) = v(2,g(n-1)). Ainsi, g(63)est le numéro de Graham. En définissant la valeur par défaut du nparamètre de la gfonction sur 63, la sortie requise peut être obtenue en appelant g()(sans paramètre), ce qui répond à nos exigences en matière de soumission de fonction sans entrée.

Vérifiez les cas v(2,1) = u(3,3,2)et les v(4,0) = u(3,5,1)tests en ligne: Python 2 , Python 3

Dyalog APL, 41 octets

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

Cas de test:

      3u 2
7625597484987

Ruby, 64 octets

Emprunter à un algorithme théorique pour calculer le nombre 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 termes simples, f a = u(3,3,a)et cela s'applique 64 fois.

J, 107 octets

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

Je travaille à la conversion uen agenda, mais pour le moment, ça ira.

F #, 111 108 octets

modifier

Ceci utilise la fonction ci-dessous pour calculer le numéro 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

Voici ma réponse précédente qui, bien, n'a pas:

Assez simple. Juste une définition de la ufonction.

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)

Usage:

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

Si je supposais 3 comme valeur pour a, je pourrais le réduire à 60:

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

Usage:

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

R, 154 142 128 126 118 octets

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)

J'ai utilisé la définition de cette fonction récursive dans Wikipédia parce que, pour une raison quelconque, la fonction suggérée ne fonctionnait pas ... ou que je craignais simplement de jouer au golf.

UPD: rasé 12 + 14 = 26 octets grâce à un conseil de Leaky Nun . La version précédente utilisait le volumineux et moins efficace

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: rasé 2 + 6 + 2 octets supplémentaires (encore une fois, félicitations à Leaky Nun ) en raison d’un remplacement ingénieux par «if (x)» au lieu de «if (x == 0)» car x <0 n’est jamais alimenté la fonction ... non?

PHP, 114 octets

ignorer les sauts de ligne; ils sont pour la lisibilité seulement.

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

Il est possible d'intégrer le deuxième cas dans le premier: pour n=1, 3^négal 3.
Cela permettra d'économiser quelques octets sur - autant que je sache - toutes les réponses existantes; enregistré deux octets sur mon

version précédente, 62 + 43 + 11 = 116 octets

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

L'associativité de gauche du ternaire nécessite des parenthèses ... ou un ordre spécifique de tests.
Cela a sauvegardé deux octets sur l'expression entre parenthèses.

Il existe probablement une approche itérative, qui pourrait permettre de continuer à jouer au golf ...
mais je ne peux pas en prendre le temps maintenant.