Extremely Deep Recursion - Part 3

It is possible to prove the following properties of $A(m,n)$ for $m<3$

$A(0,n)=n+1$

$A(1,n)=n+2$

$A(2,n)=2n + 3$

$A(3,n)=2^{n+3} - 3$

Since $A(4,5)$ is large computing the whole integer would take a while. But since all we need are the last three digits we can just find $A(m,n)$ $mod$ $1000$ at every recursive call..Ran in 0.001 seconds on my machine.

def A(m,n):
    if m == 0:
        return ( n + 1 ) % 1000
    if m == 1:
        return ( n + 2 ) % 1000
    if m == 2:
        return ( ( ( 2 * n ) + 3 ) ) % 1000 
    if m == 3:
        return ( pow( 2 , n + 3 ) - 3 ) 
    if m >0 and n == 0:
        return ( A( m - 1 , 1 ) ) % 1000
    else:
        return ( A( m - 1 , A( m , n -  1 ) ) ) % 1000

print A(4,5)

Because $m$ is rather small, we can use the table given here

$\LARGE A(4,5) = \underbrace{2^{2^{2^{2^{2^{2^{2^2}}}}}}}_{\text{eight 2's}} - 3$

We consider the last three digits of $\left ( A(4,5) + 3 \right )$ , that is modulo $1000$

$1000 = 8 \times 125$ , with $8$ and $125$ coprime positive integers, we will use Chinese Remainder Theorem

Denote $B = \left ( A(4,5) + 3 \right )$ , because $B$ has plenty of powers of $2$ 's, so $B \bmod{8} = 0$

With $\text{gcd}(2,125) = 1$ , Euler Totient Function is applicable, $\phi(125) = \phi(5^3) = 125 \left ( 1 - \frac {1}{5} \right ) = 100$

$\LARGE B \bmod{125} = 2^{2^{2^{2^{2^{2^{2^2}}}}} \bmod {100} } \bmod {125}$

Repeat: $100 = 4 \times 25$ , with $\text{gcd}(4,25) = 1$ , and $\text{gcd}(2,25) = 1$ , $\phi(25) = \phi(5^2) = 25 \left ( 1 - \frac {1}{5} \right ) = 20$

Denote $\LARGE C = \underbrace{2^{2^{2^{2^{2^{2^2}}}}}}_{\text{seven 2's}}$

$C \bmod 4 = 0$

$\large C \bmod{25} = 2^{2^{2^{2^{2^{2^2}}}} \bmod{20} } \bmod {25}$

Repeat again: $20 = 4 \times 5$ , $\text{gcd}(4,5) = 1$ , and $\text{gcd}(2,5) = 1$ , $\phi(5) = \phi(5^1) = 5 \left ( 1 - \frac {1}{5} \right ) = 4$

Denote $\LARGE D = \underbrace{2^{2^{2^{2^{2^2}}}}}_{\text{six 2's}}$ ,

$D \bmod 4 = 0$ , and by Fermat's Little Theorem

$D \bmod 5 = 2^{2^{2^{2^{2^2}}} \bmod 4 } \bmod 5 = 1$

$D$ satisfy the linear congruences:

$x_1 \equiv 0 \pmod {4}$

$x_1 \equiv 1 \pmod {5}$

By Chinese Remainder Theorem $D \bmod 20 = 16$ , consider modulo $25$

Then $C \equiv 2^{16} \equiv (2^4)^4 \equiv (16)^4 \equiv (-9)^4 \equiv 11$

Again, $C$ satisfy the linear congruences:

$\begin{aligned} x_2 & \equiv & 0 \pmod {4} \\ x_2 & \equiv & 11 \pmod {25} \\ \end{aligned}$

By Chinese Remainder Theorem $C \bmod 100 = 36$

So by considering modulo $125$

$B \equiv 2^{36} \equiv (2^7)^5 \cdot 2 \equiv 3^5 \cdot 2 \equiv -7 \cdot 2 \equiv -14 \equiv 111$

One last time, $B$ satisfy the linear congruences:

$\begin{aligned} x_3 & \equiv & 0 \pmod {8} \\ x_3 & \equiv & 111 \pmod {125} \\ \end{aligned}$

By Chinese Remainder Theorem $B \bmod {1000} = 736$

Hence,

$\begin{aligned} \left ( A(4,5) + 3 \right ) \bmod{1000} & = & 736 \\ A(4,5) \bmod{1000} & = & \boxed{733} \\ \end{aligned}$

Note: Using the same logic, the last three digits of $A(4,n)$ is $733$ for $n=2,3,4, \ldots$

The solution to this is quite simple... Looking at the function one can certainly say that its a question pertaining to a recursive function algorithm. But the answer A(4,5) is so large that it overflows the memory even for a long long int (in C++). But since the question only talks about finding the 3 digits only, just a little tweak of adding a mod 1000 for n+1 will work it out.. :D

So here's the code (in C++)

#include <iostream>
#include <conio.h>
using namespace std;

int x = 4, y = 2;

long long int A(int m, int n) {
if( m == 0 )
    return (n+1)%1000;
else if( m > 0 && n == 0 )
     return A(m-1, 1);
else if( m > 0 && n > 0 )
     return A( m-1, A(m,n-1) );
}

int main() {
cout << A(4,5);
getch();
}

I used DP memoization for this, combined with the fact that you only need the last 3 digits.. Ran in seconds. Programming language was in JavaScript.

var A=[[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]];
function a(m,n){
   if(A[m][n])return A[m][n]; 
   if(!m) return A[m][n] = n+1; 
   if(n==0 && m>0) return A[m][n] = a(m-1,1)%1000; 
   if(m>0 && n>0) return A[m][n] = a(m-1,a(m,n-1))%1000;
}

Let tower(n) denote a tower of n 2s. Some easy inductions give A(4,n) = tower(n+3) - 3.

Obviously tower(5) = 0 mod 8. But $2^8 = 16 = 2^{16}$ mod 20, so $2^{8n} = 16$ mod 20 for any n and hence tower(6) = 16 mod 20.

Similarly, $2^{16} = 36 = 2^{16+20}$ mod 100, hence tower(7) = 36 mod 100.

Finally, $2^{36} = 736 = 2^{136}$ mod 1000, so tower(8) = 736 mod 1000 and hence A(4,5) has last three digits 733.

Since we are required to print last three digits only we should pass last 3 digits only in every recursive call. The following JAVA code illustrates my idea.

public class Ackerman {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(new Ackerman().A(4, 5));
}

int A(int m, int n) {
    if (m == 0)
        return n + 1;
    else if (m > 0 && n == 0)
        return A((m - 1) % 1000, 1); // n%1000 will give last three digits
    else
        return A((m - 1) % 1000, A(m % 1000, (n - 1) % 1000));
}

}