Purely for my own amusement I've been playing around with the Ackermann function. The Ackermann function is a non primitive recursive function defined on non-negative integers by:
$A(m,n) = n+1$, if $m=0$
$A(m,n) = A(m-1,1)$, if $m>0$ and $n=0$
$A(m,n) = A(m-1,A(m,n-1))$, if $m>0$ and $n>0$
I'm not interested in values of the function itself, rather I'm interested in the number of recursions the function takes to arrive at a value. For example:
$A(1,2) = A(0,A(1,1)) = A(0,A(0,A(1,0))) = A(0,A(0,A(0,1))) = A(0,A(0,2)) = A(0,3) = 4$
That's 6 steps, so if we define $RA(m,n)$ as the number of recursions to calculate $A(m,n)$, then $RA(1,2) = 6$.
I made a short Excel macro to calculate $RA(m,n)$ for any given $m$ and $n$. The problem I have is that $RA(m,n)$ grows even faster than $A(m,n)$ and I quickly run out of stackspace. The table below shows $RA(m,n)$ for very small values of $m$ and $n$. The numbers shown for $RA(3,10)$ and $RA(4,1)$ are the number of steps before crashing!
A formula for $RA(1,n)$ is trivial, and it is relatively easy to see that $RA(2,n) = 5(n+1) + 4n(n+1)/2$.
So my questions: can anyone see an explicit formula for $RA(3,n)$? More generally, does a formula exist for $RA(m,n)$, in the same way that $A(m,n)$ can be expressed using Knuth arrows?
For the low values shown of $m$ and $n$, $RA(m,n)$ looks about order of magnitude larger than $A(m,n)$. Can we prove that $RA(m,n) > A(m,n)$ for all $m,n$. Intuitively, it should be.
For bonus points, can $RA(m,n)$ be expressed in terms of $A(m,n)$?