Theoretically output Graham's number

Question

Graham's number \$G\$ is defined in this way:

\begin{align*} u(3,n,1) & = 3^n \\ u(3,1,m) & = 3 \\ u(3,n,m) & = u(3,u(3,n-1,m),m-1) \end{align*}

Then,

\begin{align*} g_1 & = u(3,3,4) \\ g_2 & = u(3,3,g_1) \\ g_3 & = u(3,3,g_2) \\ & \vdots \\ G & = u(3,3,g_{63}) \end{align*}

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

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 10

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 11

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

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 14

Dyalog APL, 41 bytes

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

Test case:

      3u 2
7625597484987

Answer 15

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 16

Jelly, 22 bytes

’ß’ß’}ð‘3*ða?
4’2çƊ64¡

Try it online!

I believe this is close to identical to Dennis' deleted Jelly answer but was developed independently and uses a language feature that wasn't available at the time of his answer.

The first line defines a function \$v(n, m) = u(3, n+1, m+1)\$ and the TIO footer demonstrates this for \$u(3, 3, 2)\$, \$u(3, 5, 1)\$ and \$u(3, 1, 5)\$.

With our defined \$v\$, we then have the recurrence relation

\begin{align*} g_1 & = v(2, 3) \\ g_{i+1} & = v(2, g_i - 1) \\ G = g_{64} & = v(2, g_{63} - 1) \end{align*}

A more standard approach, which defines \$w(n, m) = u(3, n, m)\$ and then uses

\begin{align*} g_1 & = w(3, 4) \\ g_{i+1} & = w(3, g_i) \\ G = g_{64} & = w(3, g_{63}) \end{align*}

comes out at 23 bytes:

3*ð’ßṛß’}ð«Ị¥?
4 3ç$64¡

Try it online!

How they work

\$v(n, m)\$

’ß’ß’}ð‘3*ða? - Helper link, v(n, m). Takes n on left, m on right
            ? - If:
           a  -   n and m are both non-zero
      ð       - Then:
’             -   n-1
 ß            -   v(n-1, m)
  ’           -   v(n-1, m)-1
    ’}        -   m-1
   ß          -   v(v(n-1, m)-1, m)
          ð   - Else:
       ‘      -   n+1
        3*    -   3^(n+1)

4’2çƊ64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    Ɗ    - Last 3 links as a monad f(x):
 ’       -   x-1
  2ç     -   v(2, x-1)
     64¡ - Starting with x = 4, iterate f(x) 64 times

\$w(n, m)\$

3*ð’ßṛß’}ð«Ị¥? - Helper link, w(n, m). Takes n on left, m on right
            ¥? - If:
          «    -   min(n, m)
           Ị   -   is insignificant (abs(x) ≤ 1)
  ð            - Then:
3*             -   3^n
         ð     - Else:
   ’           -   n-1
     ṛ         -   m
    ß          -   w(n-1, m)
       ’}      -   m-1
      ß        -   w(w(n-1, m), m-1)

4 3ç$64¡ - Main link. No arguments
4        - Set the return value and left argument to 4
    $    - Last two links as a monad g(x):
  3ç     -  w(3, x)
     64¡ - Starting with x = 4, iterate g(x) 64 times

Answer 17

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 18

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 19

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 20

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.