In

Perl, using the

Math::BigInt package so it can handle

large numbers:

#!/usr/bin/perl
use Math::BigInt; # mmm... bignums
# Yes, it's a bug that neither input value can be 0. A(0, n) is trivial,
# while A(m, 0) = A(m-1, 1)
($x=shift) && ($y=shift) || die "usage: $0 m n\n";
$m=Math::BigInt->new($x);
$n=Math::BigInt->new($y);
print Ack($m, $n), "\n";
sub Ack{
my $m=shift;
my $n=shift;
return $n+1 if $m==0; # Ack(0,n)=n+1
# If $n==0, then $n+1==1 which is what we want
return Ack($m-1, $n+1) if $n==0; # Ack(m,0)=Ack(m-1,1)
return Ack($m-1, Ack($m, $n-1)); # Ack(m,n)=Ack(m-1, Ack(m, n-1))
}

However, A(1, n) = A(0, A(

1,

n-1)) = A(1, n-1)+1 =

... = A(1, n-n)+n = A(1, 0)+n = A(0, 1)+n = 1+1+n = n+2, not 2n as claimed above. (

Note that A(1, n)

= A(0, A(0, ... A(0, 1)...)), again

not as

above).

Since we know A(1, n), A(2, n) = A(1, A(2, n-1)) = A(2, n-1)+2 = ... = A(2, n-n)+2n = A(2, 0)+2n = A(1, 1)+2n = 1+2+2n = 2n+3.

Similarly, A(3, n) = 2^{n+3}-3 (that's 2**(n+3)-3), and A(4, n) = 2^^(n+3)-3 (where ^^ is the iterated power operation). You can greatly speed up the program above by adding cases for these.

My favorite number is A(4, 2).