Ackermann's Function

Question

$A(m,n) = n+1$ if $m=0$
$A(m,n) = A(m-1,1)$ if $n=0$
$A(m,n)= A(m-1,A(m,n-1))$
This function blows off( I mean increases drastically) after a certain point. For example,$ A(2,4) = A(1,A(2,3)) = A(1,A(1,A(2,2))) = A(1,A(1,A(1,A(2,1)))) = 11$ But, $A(4,2) = 2^{65536}-3$
I want to find the $20th$ digit of $A(4,5)$ from the rear end. Is there any efficient algorithm for this? I tried to code in Matlab, but for more than 5000 recursions, The program crashes. I was unable to do even $A(4,3)$.

---

My code:

function [r] = A(m,n) 
if(m==0)
    r=n+1;
elseif(n==0)
    r=A(m-1,1);
else
    r=A(m-1,A(m,n-1));
end
end 

As you can see, it's a straight forward algorithm which has the worst case recursions. Can you suggest a better algorithm to implement?

Answer 1

You'd have to use modular mathematic. The powers of 2 repeat after 19 times in mod. Try to use that.