Extremely Deep Recursion - Part 3

The Ackermann function is a computable function which grows very, very quickly as its inputs grow. For example, while A(1,2), A(1,2), A(2,2),A (2,2), and A(3,2)A(3,2) are equal to 4,7,4,7, and 29,29, respectively, A(4,2)2×1019728 A(4,2) \approx 2 \times 10^{19728} .

The Ackermann function can be defined as follows: A(m,n)={n+1if m=0A(m1,1)if m>0 and n=0A(m1,A(m,n1))if m>0 and n>0. A(m,n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}

What are the last 3 digits of A(4,5)? A(4,5) ?

×

Problem Loading...

Note Loading...

Set Loading...