Graham’s number, as huge as it is, can be “described” or “named” in a very few symbols. Several people sent us programs that (in principle!) calculate Graham’s number— you can think of any of these programs as notation for Graham’s number.

(It looks like Graham’s number can be written out in about 100-200 symbols– but it is very special. Here’s a puzzle: for a generic number, how many symbols are required?)

How to encode Graham’s number

Really, there’s only way to go about it:

First of all, you need a bit to work out what a^^..(n arrows)..^^ b is
Let’s call this u(a,b,n). We can’t compute this directly, but we can compute it in terms of simpler, similar kinds of expressions. For example, note that

a (n arrows) b = a (n-1 arrows) a (n-1 arrows) a (n-1 arrows) a …. (b a’s all together) = a (n-1 arrows) (a (n-1 arrows) b-1 times)

For example, 3^^^4 = 3^^3^^3^^3 = 3 ^^ (3^^3^^3) = 3 ^^ (3^^^3)

In other words, we have the identity that

u(a,b,n) = u(a, u(a,b-1,n), n-1)

We can work out 3^^^4, for example, by working out the simpler expression 3^^^3 first.
In turn, working out 3^^^3 will require knowing 3^^^2, which will require knowing 3^^^1.
But

u(a,1,n) = a

Similarly, we also have u(a,b,1) = a^b, or if our programming language doesn’t include exponentiation, we can go further and use u(a,b,0) = a x b.

So in order to work out u(a,b,n) we use the relations:

u(a,b,n) = u(a, u(a,b-1,n), n-1) for b,n>1
u(a,1,n) = a
u(a,b,0) = a b

For example, to work out
u(3,3,4) = 3^^^^3, we find that
u(3,3,4) = u(3, u(3,2,4), 3)
So we need to work out u(3,2,4):
u(3,2,4) = u(3,u(3,1,4),3);
So we need to work out u(3,1,4):
u(3,1,4) = 3

Now back to the beginning: u(3,3,4) = u(3, u(3,2,4), 3) = u(3, 7625597484987, 3) This looks like a mess, but notice that n is now lower. A mere 7625597484987 more steps, and we will have reduced ourselves to u(3, something big, 2). ETC.

Now Graham’s number is defined in a similar way:

let G(1) = u(3,3,4)
Let G(k) = G(3,3, G(k-1)) for k>1

Then Graham’s number is simply G(64)

Various programs to implement the above:

Math
For all a,b,n, with b,n>1 let u(a,b,n)=u(a,u(a,b-1,n), n-1); let u(a,b,0) = ab; and let u(a,1,n) = a.
Let G(1) = u(3,3,4) and for all k>1, let G(k) = u(3,3,G(k-1)). Consider G(64).

Mathematica

u[a_,b_,0]:=a b
u[a_,1,n_]:=a
u[a_,b_,n_]:=u[a,u[a,b-1,n],n-1]
G[1]:=u[3,3,4]
G[k_]:=u[3,3,G[k-1]]
G[64]

Scheme (sent in by Jay McCarthy)

(module graham mzscheme
(define (up a b n)
(cond [(= n 1) (expt a b)]
[(= b 0) 1]
[else (up a (up a (sub1 b) n) (sub1 n))]))
(define (g i)
(up 3 3 (if (= i 1) 3 (g (sub1 i)))))
(define graham (g 64)))

Java (sent in by Adam Higgens)

import java.lang.Math;
public class Graham{
public static int hyper(int a, int n, int b){
if(n==1){
return Math.pow(a,b);
}
else if(b==1){
return a;
}
else{
return hyper(a, n-1, hyper(a, n, b-1));
}
}
public static int graham(int n){
if (n==1){
return hyper(3,4,3);
}
else{
return hyper(3, graham(n-1), 3);
}
}
public static void main(String[] args){
System.out.println(graham(64));
}
}