Theoretically output Graham's number

Question

Graham's number G is defined in this way:

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)

You are given that u(3,3,2)=7625597484987 to check your code.

Your task is to write a program/function that will output the value of G deterministically, given enough integer size and enough time.

References

• Graham's number
• Knuth's up-arrow notation
• Conway chained arrow notation

Leaderboard

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>

Answer 1

Binary lambda calculus, 114 bits = 14.25 bytes

Hexdump:

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

Binary:

010001000101011101000010101100000010110110001000000111111001110101110100000011100101111011010000001110011100111010

Explanation

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

This is (λ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, where all numbers are represented as Church numerals. Church numerals are the standard lambda calculus representation of natural numbers, and they are well suited to this problem because a Church number is defined by function iteration: n g is the nth iterate of the function g.

For example, if g is the function λn. λf. 3 (n f) that multiplies 3 by a Church numeral, then λn. n g 1 is the function that takes 3 to the power of a Church numeral. Iterating this operation m times gives

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

(We use multiplication u(–, –, 0) rather than exponentiation u(–, –, 1) as the base case, because subtracting 1 from a Church numeral is unpleasant.)

Substitute n = 3:

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

Iterating that operation 64 times, starting at m = 4, gives

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

To optimize this expression, substitute 64 = 4^3 = 3 4:

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

Remember 4 = succ 3 = λf. λz. f (3 f z) as a lambda argument:

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

Finally, remember 3 = λf. λz. f (f (f z)) as a lambda argument:

(λ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.

Answer 2

Haskell, 41 bytes

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

Explanation:

(`i`1)f n = i f 1 n computes the nth iterate of the function f starting at 1. In particular, (`i`1)(*3)n = 3^n, and iterating this construction m times gives i(`i`1)(*3)m n = u(3, n, m). We can rewrite that as (($n).i(`i`1)(*3))m = u(3, n, m), and iterate this construction k times to get i(($3).i(`i`1)(*3))4 k = g_k.

Answer 3

Haskell, 43 bytes

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

There has be a better way to flip g inline.

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

Just writing down the definitions.

The base cases are a bit cleaner backed up to 0, though it saves no bytes. Perhaps it will make it easier to write an alternate definition.

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

Answer 4

Pyth, 25 bytes

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

The first part M?H.UgbtH*G]3^3G defines a method g(G,H) = u(3,G,H+1).

To test the first part, check that 7625597484987=u(3,3,2)=g(3,1): g3 1.

The second part ug3tG64 4 starts from r0 = 4 and then compute rn = u(3,3,r(n-1)) = g(3,r(n-1)) 64 times, outputting the final value (r is chosen instead of g to avoid confusion).

To test this part, start from r0=2 and then compute r1: ug3tG1 2.

Answer 5

Sesos, 30 bytes

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

Disassembled

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

Or in Brainfuck notation:

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

Testing

To compute u(3, n, u(3, n, … u(3, n, m) … )) with k nested calls to u, replace the first three add instructions add 4, add 64, add 3 with add m, add k, add n, respectively. Because Sesos can’t build numbers faster than in linear time, you’re practically limited to small values like u(3, 2, 2) = 27, u(3, 5, 1) = 243, and u(3, 1, u(3, 1, … u(3, 1, m) … )) = 3.

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

Answer 7

Brachylog, 57 bytes

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

Expects no Input nor Output and writes the result to STDOUT. This will produce a stack overflow at one point.

To check that this works for small values (e.g u(3,3,2)) you can replace the 4 with the value of m and 64 with 1.

Explanation

This is basically a straightforward implementation of the explained way of computing the number.

• Main predicate:

  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
  

• Predicate 1:

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

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

Answer 8

Caramel, 38 bytes

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

This is syntactic sugar for the lambda calculus expression 64 (λm. m (λf. λn. n f 1) (λn. λf. 3 (n f)) 3) 4, where all numbers are represented as Church numerals.

Answer 9

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

To output Graham's number, query for g(64,G). (if the 8 bytes of this query are to be counted, the length is 137 bytes):

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

But as can be expected, this runs out of stack.

Test

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

Backtracking causes it to run out of stack:

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

Ungolfed

The ungolfed version adds the general up-arrow notation, not just for 3, and uses cuts and checks to avoid backtracking and undefined situations.

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

Answer 10

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: saved 11 bytes by removing tabs and newlines. EDIT: thx auhmann saved another byte and fixed my program

Answer 11

Mathematica, 59 bytes

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

Uses an undefined infix operator ± which requires only 1 byte when encoded in ISO 8859-1. See @Martin's post for more info. Mathematica functions support pattern matching for their arguments, such that the two base cases can be defined separately.

Answer 12

C, 114 109 bytes

Based on the answer by @thepiercingarrow (link) I golfed the answer down quite a bit. Most savings are due to the abuse of default typing of arguments when doing K&R style functions and replacement of if statements with ternary operators. Added optional newlines between functions for readability.

Improved to 109 thanks to @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));}

Answer 13

Ruby, 64 bytes

Borrowing from Theoretical algorithm to compute Graham's number.

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

Simply put, f a = u(3,3,a) and it applies this 64 times.

Answer 14

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)

The v function defines the same function as the one found in Dennis's answer: v(n,m) = u(3,n+1,m+1). The g function is a zero-indexed version of the traditional iteration: g(0) = v(2,3), g(n) = v(2,g(n-1)). Thus, g(63) is Graham's number. By setting the default value of the n parameter of the g function to 63, the required output can be obtained by calling g() (with no parameters), thus meeting our requirements for a function submission which takes no input.

Verify the v(2,1) = u(3,3,2) and v(4,0) = u(3,5,1) test cases online: Python 2, Python 3

Answer 15

Dyalog APL, 41 bytes

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

Test case:

      3u 2
7625597484987

Answer 16

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

I'm working on converting u to an agenda, but for now it'll do.

Answer 17

F#, 111 108 bytes

Edit

This is using the function below to calulcate Graham's number

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

Here's my previous answer which, well, didnt:

Pretty straightforward. Just a definition of the u function.

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

If I assumed 3 as the value for a, I could cut it to 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

Answer 18

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)

I used the Wikipedia definition of this recursive function because for some odd reason the suggested one did not work... or I just suck at R golfing.

UPD: shaved off 12+14=26 bytes thanks to a tip from Leaky Nun. The prior version used the bulky and less efficient

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: shaved off 2+6+2 more bytes (again, kudos to Leaky Nun) owing to an ingenious replacement with “if(x)” instead of “if(x==0)” because x<0 is never fed into the function... right?

Answer 19

PHP, 114 bytes

ignore the line breaks; they are for readability only.

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

It is possible to integrate the second case into the first one: for n=1, 3^n equals 3.
This will save a few bytes on - as far as I can see - all existing answers; saved two bytes on my

previous version, 62+43+11=116 bytes

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

PHP´s left associativity of the ternary requires parentheses ... or a specific order of tests.
This saved two bytes on the parenthesized expression.

---

There is probably an iterative approach, which may allow further golfing ...
but I can´t take the time for it now.