The Ackermann Function

$\def\htmltext#1{\style{font-family:inherit;}{\text{#1}}}$

For non-negative integers $m$, $n$, the Ackermann function $A(m,n)$ is defined as follows:

$$
A(m,n) = \cases{
n+1 &$\htmltext{ if }m=0$\cr
A(m-1,1) &$\htmltext{ if }m>0 \htmltext{ and } n=0$\cr
A(m-1,A(m,n-1)) &$\htmltext{ if }m>0 \htmltext{ and } n>0$\cr
}$$

For example $A(1,0) = 2$, $A(2,2) = 7$ and $A(3,4) = 125$.

Find $\displaystyle\sum_{n=0}^6 A(n,n)$ and give your answer mod $14^8$.

Let’s calculate the sum by substituting $n$ from 0 to 6 into the Ackermann function $A(n, n)$, as defined above.

– When $n = 0$, $A(n, n) = A(0, 0) = 1$.
– When $n = 1$,
$A(n, n) = A(1, 1) = A(0, A(1, 0)) = A(0, A(0, 1)) = A(0, 2) = 3$.
– When $n = 2$,
$A(n, n) = A(2, 2) = A(1, A(2, 1)) = A(1, A(1, 1)) = A(1, 3) = A(0, A(1, 2)) = A(0, 4) = 5$.
– When $n = 3$,
$A(n, n) = A(3, 3) = A(2, A(3, 2)) = A(2, A(2, A(3, 1))) = A(2, A(2, A(2, 2))) = A(2, A(2, 7)) = A(2, 16)$.
– The Ackermann function is well known to grow extremely rapidly. To find more values for larger $n$, we have to follow the definitions strictly and iteratively which unfortunately is not practical by hand or using standard computational capabilities, for $n\geq4$.

However, by using the properties of modulo operation, we can calculate $\displaystyle\sum_{n=0}^6 A(n,n)$ mod $14^8$.

We know that, (a + b) mod n = [(a mod n) + (b mod n)] mod n.

Applying this property here,

$\displaystyle\sum_{n=0}^6 A(n,n) = A(0,0) + A(1,1) + A(2,2)+ A(3,3) + A(4,4)+ A(5,5) + A(6,6) \mod 14^8$

The sum becomes:

$= [(A(0,0) \mod 14^8) + (A(1,1) \mod 14^8) + (A(2,2) \mod 14^8) + (A(3,3) \mod 14^8)+ (A(4,4) \mod 14^8)+ (A(5,5) \mod 14^8) + (A(6,6) \mod 14^8)] \mod 14^8$

Substituting the values we have already calculated,

$= [1 + 3 + 5 + 16 + A(4,4)+ A(5,5) + A(6,6)] \mod 14^8$

Unfortunately, as said before, manually computing the Ackermann function for inputs larger than 3 is impractical due to its extremely rapid growth.

More Answers: