# Ackermann

#### Problem

Let $f$ be a function defined by the following:

1. $f(0, n) = n + 1$
2. $f(m+1, 0) = f(m, 1)$
3. $f(m+1, n+1) = f(m, f(m+1, n))$

being $m$ and $n$ natural numbers.

What is the value of $f(4, 1981)$?

#### Solution

Let’s start with the values of $f(1, n)$:

$f(1, n) = f(0, f(1, n-1))$ (Eq. 3)

$f(1, n) = f(1, n-1) + 1$ (Eq. 1)

Continuing the process we get

$f(1, n) = f(1, n-n) + n = f(1, 0) + n$

$f(1, n) = f(0, 1) + n$ (Eq. 2)

$f(1, n) = 1 + 1 + n = n + 2$ (Eq. 1)

ending with the expression

$f(1, n) = n + 2$.

Now we can try to get the values of $f(2, n)$:

$f(2, n) = f(1, f(2, n - 1)) = f(2, n - 1) + 2$ (Eq. 3).

Repeating the process we end with

$f(2, n) = f(2, n - n) + 2n = f(2, 0) + 2n$

$f(2, n) = f(1, 1) + 2n = 1 + 2 + 2n = 2n + 3$

$f(2, n) = 2n + 3$.

Using this result to get $f(3, n)$:

$f(3, n) = f(2, f(3, n - 1)) = 2 f(3, n-1) + 3$.

Iterating this process we reach

$f(3, n) = 2 f(2, f(3, n - 2)) + 3 = 2 (2 f(3, n-2) + 3) + 3 = 2^2 f(3, n-2) + 3(2^1 + 2^0)$

$f(3, n) = 2^2(2 f(3, n-3) + 3) + 3(2^1 + 2^0) = 2^3 f(3, n-3) + 3(2^2 + 2^1 + 2^0)$

$f(3, n) = 2^n f(3, 0) + 3(2^n - 1)$

$f(3, n) = 2^n f(2, 1) + 3(2^n - 1)$ (Eq. 2)

$f(3, n) = 2^n 5 + 3(2^n - 1) = 8 2^n - 3 = 2^{n+3} - 3$

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

$f(4, n)$ is finally in sight 😀 Replacing:

$f(4, n) = f(3, f(4, n - 1))$ (Eq. 3)

$f(4, n) = 2^{f(4, n - 1)+3} - 3 = 2^3 2^{f(4, n - 1)} - 3$.

Making some additional iterations to get the pattern:

$f(4, n) = 2^3 2^{f(3, f(4, n - 2))} - 3$ (Eq. 3)

$\displaystyle f(4, n) = 2^3 2^{2^{f(4, n - 2)+3} - 3} - 3$

$\displaystyle f(4, n) = 2^3 2^{-3} 2^{2^3 2^{f(4, n - 2)}} - 3 = 2^{2^3 2^{f(4, n - 2)}} - 3$

$\displaystyle f(4, n) = 2^{2^3 2^{2^3 2^{f(4, n - 3)} - 3}} - 3$ (Eq. 3)

$\displaystyle f(4, n) = 2^{2^{2^3 2^{f(4, n - 3)}}} - 3$

Now the progression is clear: each iteration adds one 2 to the exponential tower and the $2^3$ term moves with $f$. Let’s define a function to encapsulate the tower exponential:

$\mathrm{tow}(0, k) = k$

$\mathrm{tow}(n+1, k) = 2^{\mathrm{tow}(n, k)}$

($\mathrm{tow}(n, 1)$ corresponds to a tower of $n$ 2s).

Then we can iterate until reaching

$f(4, n) = \mathrm{tow}\left(n-1, 2^3 2^{f(4, n - n)}\right) - 3 = \mathrm{tow}\left(n-1, 2^{3 + f(4, 0)}\right) - 3$

$f(4, n) = \mathrm{tow}\left(n, 3 + f(4, 0)\right) - 3$.

Getting $f(4, 0)$:

$f(4, 0) = f(3, 1) = 2^{1+3} - 3 = 13$

Replacing:

$f(4, n) = \mathrm{tow}\left(n, 16\right) - 3 = \mathrm{tow}\left(n, 2^{2^2}\right) - 3 = \mathrm{tow}\left(n + 3, 1\right) - 3$

#### Final result

Then the asked for value is $f(4, 1981) = \mathrm{tow}\left(1984, 1\right) - 3$ in our notation.