# Theoretically output Graham's number

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

• – Leaky Nun Jun 27 '16 at 7:30
• Is randomness allowed? If I just output random values, eventually Graham's number must be produced. – miles Jun 27 '16 at 7:33
• @miles Why on earth isn't it already a standard loophole? Clarified. – Leaky Nun Jun 27 '16 at 7:35
• Warning: u(3, 3, 2) = u(3, 2, 3) = 7625597484987, so you’ll also want to test on other values such as u(3, 5, 1) = 243 to make sure you got the argument order right. – Anders Kaseorg Jun 27 '16 at 10:09
• Graham's number? – Beta Decay Aug 9 '16 at 10:47

# 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 ym. mg. λ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

mg. λ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:

mg. λ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. mg. λ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. mg. λ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 ym. mg. λ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 ym. mg. λn. n g 1) (λn. λf. x (n f)) x) y) (λf. λz. f (x f z))) 3 = G.

• Where could one find an interpreter for this language? – Dennis Jun 28 '16 at 0:30
• @Dennis tromp.github.io/cl/cl.html has a couple of them. – Anders Kaseorg Jun 28 '16 at 0:32
• This is awesome. this deserves a sizeable bounty – cat Jun 28 '16 at 18:19
• 14.25 bytes seems to be messing up the leaderboard. It is parsed as 25 bytes, and you are therefore placed as second. – Dan Jun 28 '16 at 19:05
• @Dan I fixed the leader board snippet, I think. – Anders Kaseorg Jun 28 '16 at 19:43

i=((!!).).iterate
i(($3).i(i1)(*3))4 64 Explanation: (i1)f n = i f 1 n computes the nth iterate of the function f starting at 1. In particular, (i1)(*3)n = 3^n, and iterating this construction m times gives i(i1)(*3)m n = u(3, n, m). We can rewrite that as (($n).i(i1)(*3))m = u(3, n, m), and iterate this construction k times to get i(($3).i(i1)(*3))4 k = g_k. ## Haskell, 43 bytes q=((!!).).iterate g=q(q1)(3*) q(g3)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
• Can you use another function which has precedence lower than + so as to remove the parentheses between m-1? – Leaky Nun Jun 27 '16 at 9:46
• I count 44 bytes, and what happened to 4 and 64? – Leaky Nun Jun 27 '16 at 9:49
• Oops, I copied in my smaller-parameter test. I don't think I can change the operator precedence because I'm defining a new function and those have a default precedence. I can't overwrite an existing function. – xnor Jun 27 '16 at 9:53
• I mean, I count 44 bytes after you change it back to 64. – Leaky Nun Jun 27 '16 at 9:54
• I think you mean (g3), not (3g). – Anders Kaseorg Jun 27 '16 at 10:47

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

• If g(G, H) = u(3, G, H + 1), you should have r(n) = u(3, 3, r(n − 1)) = g(3, r(n − 1) − 1), not g(3, r(n − 1)). I think your code is right but your explanation is missing the − 1. – Anders Kaseorg Jun 29 '16 at 9:25
• You can save a byte by using unoffsetted u arguments (^3*3, tGG), and another byte with .UgbtH*G]3e.ugNtHG1. – Anders Kaseorg Jun 29 '16 at 9:43
• An alternate way to save that second byte is *G]3ShG. – Anders Kaseorg Jun 29 '16 at 9:54

# 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. • You can replace [-] with , since EOF is 0. – mbomb007 Jul 22 '16 at 13:37 ## 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) • @AndersKaseorg Ugh, in that case I might as well revert that change. – Neil Jun 29 '16 at 8:29 • This causes a stack overflow, might need to recheck your reccursion pattern. – NodeNodeNode Oct 19 '17 at 15:07 • This isn't simple ES7. This is unbounded ES7 (an imaginary variant of ES7 but with bignum, able to oracle infinitely, and is using decimal with /#xE^ as shorthand). – user75200 Jan 13 '18 at 18:58 # 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) # 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. mf. λn. n f 1) (λn. λf. 3 (n f)) 3) 4, where all numbers are represented as Church numerals. • (n f->3 (n f)) shouldn't it read n-1? – Leaky Nun Jun 27 '16 at 23:14 • @LeakyNun No. (n f->3 (n f)) is a function for multiplication by three in Church numerals. – Anders Kaseorg Jun 27 '16 at 23:26 • This challenge seems excessively simple in lambda calculus. Why? – cat Jun 28 '16 at 18:22 # 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). • How did you manage to do it without having the number 64 anywhere in your code? – Leaky Nun Jun 28 '16 at 12:34 • @LeakyNun I edited to clarify; better? – SQB Jun 28 '16 at 12:51 • Well, then add it into your code as well as your byte-count. – Leaky Nun Jun 28 '16 at 12:52 # 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 • You could remove g(int a){if(a==1)return u(3,4);return g(a-1);} since it's not being used at all... Or are you forgetting something? – auhmaan Jun 29 '16 at 15:10 • @auhmaan oops sorry, I used that number for testing and forgot to change it back. Thanks!! – thepiercingarrow Jun 29 '16 at 19:46 • Your return g(a-1) should be return u(3,g(a-1)). – Anders Kaseorg Jun 29 '16 at 23:40 • I don't know if I should make a proper answer or just comment on this, but you can get this solution down to 114 bytes quite easily by realizing: Newlines between functions can be omitted. Omitting types for all argumens default them to int (think K&R). If statements like these can be written with nested ternary ops. Code: 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 Jul 16 '16 at 21:16 • @algmyr wow amazing! you should go post your own answer XD. – thepiercingarrow Jul 18 '16 at 3:05 # 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. • Since when did Mathematica use ISO 8859-1? – Leaky Nun Jun 27 '16 at 23:17 • n_ ±m_:=Nest[#±(m-1)&,3,n] – Leaky Nun Jun 27 '16 at 23:23 # 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));} • g(a){return u(3,a<2?4:g(a-1));} – Leaky Nun Jul 21 '16 at 13:13 • @LeakyNun That's a really good one. Thanks. – algmyr Jul 21 '16 at 13:17 ## 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 • It's kinda hard to verify, but your function g seems off. Shouldn't v(2,n-1) be g(n-1) or something similar? – Dennis Jun 29 '16 at 7:21 • @Dennis Good catch. I'll fix that. – Mego Jun 29 '16 at 7:57 • Actually the offset between u and v means it should be g(n-1)-1. – Anders Kaseorg Jun 29 '16 at 8:28 • @AndersKaseorg I should not do programming while sleepy. I have to re-learn this every few days. – Mego Jun 29 '16 at 8:29 • @AndersKaseorg In the future, please do not edit other people's submissions, even if it is to fix a mistake in an improvement/bugfix that you suggested. – Mego Jun 29 '16 at 8:40 ## Dyalog APL, 41 bytes u←{1=⍺:3⋄1=⍵:3*⍺⋄(⍵∇⍨⍺-1)∇⍵-1} 3u 3u⍣64⊣4 Test case: 3u 2 7625597484987 • You should be able to convert 1=⍺:3⋄1=⍵:3*⍺ to just 1=⍵:3*⍺ (3=3*1) – Zacharý Jul 31 '17 at 22:01 # 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. • A good explanation on why and how this code works would be nice. – Manish Kundu Nov 16 '18 at 6:36 • It is a straightforward application of the definition of Graham's number. – Simply Beautiful Art Nov 21 '18 at 18:27 # 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.

• Something like u=:3^[[:(3$:])/[#<:@]@.*@] (not tested) – Leaky Nun Jun 28 '16 at 22: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 • The challenge is to write Graham’s number, not u. You can of course include any intermediate functions you need, such as u with or without its first argument fixed at 3. – Anders Kaseorg Jul 22 '16 at 2:19 • @AndersKaseorg edited that in. Thanks. My previous comment seems to have disappeared. – asibahi Jul 22 '16 at 4:08 ## R, 154142128126 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? • @LeakyNun Thank you, updated the answer with acknowledgement. – Andreï Kostyrka Jul 22 '16 at 17:45 • Just a sec... Today is my first day of code golfing, there is much to learn! – Andreï Kostyrka Jul 22 '16 at 17:47 • You are invited to join our chat. – Leaky Nun Jul 22 '16 at 17:48 • More golfing, please see the improvement. – Andreï Kostyrka Jul 22 '16 at 17:52 • Ta-dam, done, changed the function u in the same key as your g and saved 6 more bytes—awesome! – Andreï Kostyrka Jul 22 '16 at 18:42 # 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.

• wish I knew Sesos or had the time to learn it and translate right now – Titus Jul 25 '16 at 12:11
• @Leaky Nun: I broke it down to only loops and addition. Is there a way in Sesos to add the value of one cell to another? – Titus Jul 25 '16 at 13:04
• @AndersKaseorg: You´re probably right ... I got blisters on my eyeballs from looking at that algorithm. Will look at it again soon. – Titus Jul 26 '16 at 3:31