## Follow-up: Graham’s Number

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

Thus u(3,2,4) = u(3,3,3). Now u(3,3,3) = u(3, u(3,2,3),2);

u(3,2,3)= u(3,u(3,1,3),2) = u(3,3,2) = u(3,u(3,2,2),1) = 3 ^ u(3,2,2) = 3 ^ u(3,u(3,1,2),1) = 3 ^ (3^ u(3,1,2)) = 3 ^ (3 ^ 3) = 3^ 27 = 7625597484987

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:=u[3,3,4]
G[k_]:=u[3,3,G[k-1]]
G

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

1. ### rmjarvis said,

April 13, 2007 at 8:43 am

Here is a C progam that would print out Graham’s number if it could store infinitely large integers:

#include

int f(int a, int b, int c)
{
int i,x;
if(c==1) for(x=1;b>0;–b) x *= a;
else {
x = f(a,b,–c);
for(i=c;i>0;–i) x = f(a,x,c);
}
return x;
}

int g(int n)
{
return n==1 ? f(3,3,4) : f(3,3,g(n-1));
}

int main()
{
return printf(“%d\n”,g(64));
}

Basically, g(n) is the nth number in Graham’s sequence, for which g(64) is Graham’s number. f(a,b,c) is a^^^…^^^b where there are c ^’s in there.

It’s probably a bit longer than the Fortran version, since C doesn’t have any native integer exponent function, so I had to write my own (the c==1 case at the start of the f function.)

2. ### nklein said,

April 13, 2007 at 8:51 am

Here are some snippets of Smalltalk code that one could add to the Integer class to compute the numbers in the Graham number sequence. And, since Smalltalk already uses arbitrary-precision integers, you should be down the road:

graham
self < 1
ifTrue: [ self error: ‘Only supports positive graham indexes.’ ].
self = 1
ifTrue: [ ^ 3 arrow: 3 arrowCount: 4. ].
^ 3 arrow: 3 arrowCount: ( ( self-1 ) graham ).

and then the arrow notation method:

arrow: power arrowCount: count
power < 0
ifTrue: [ self error: ‘Negative power is a problem.’. ].
count < 1
ifTrue: [ self error: ‘Must have at least one arrow.’. ].
power = 0
ifTrue: [ ^ 1. ].
count = 1
ifTrue: [ ^ self * ( self arrow: (power-1) arrowCount: count ). ].
^ self arrow: ( self arrow: (power-1) arrowCount: count ) arrowCount: (count-1).

So, to get the first graham number, one would do: `1 graham`. However, you best be able to interrupt it, because even the first number in the series is immense.
Anyhow, that’s 16 lines of code… 6 of which are error checking.