11,335
pages

Sudan function is a fast growing function discovered by Gabriel Sudan. It is similar to the Ackermann function (but less well-known) and formally defined as follows:

$$F_0(x,y) = x+y$$

$$F_{n+1}(x,0) = x$$ (for $$n \geq 0$$)

$$F_{n+1}(x,y+1) = F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)$$ (for $$n \geq 0,y \geq 0$$)

It has been proven that the function is not primitive recursive.

## Values

It can be shown that $$F_1(x,y) = F_1(0,y)+2^y \times x$$. Below is the table for values of $$F_2(n)$$.

y \ x 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 8 27 74 185 440
2 19 10,228 $$\approx 1.55 \times 10^{10}$$ $$\approx 5.74 \times 10^{24}$$ $$\approx 3.67 \times 10^{58}$$ $$\approx 5.08 \times 10^{135}$$