A260002 Sudan Numbers: a(n)= f(n,n,n) where f is the Sudan function.

0, 3, 15569256417

Offset: 0

Author

Natan Arie Consigli, Jul 12 2015

Keywords

• nonn
• bref

Comments

The Sudan function is the first discovered not primitive recursive function that is still totally recursive like the well-known three-argument (or two-argument) Ackermann function ack(a,b,c) (or ack(a,b)).

The Sudan function is defined as follows:

f(0,x,y) = x+y;

f(z,x,0) = x;

f(z,x,y) = f(z-1, f(z,x,y-1), f(z,x,y-1)+y).

Just as the three-argument (or two-argument) Ackermann numbers A189896 (or A046859) are defined to be the numbers that are the answer of ack(n,n,n) (or ack(n,n)) for some natural number n, the Sudan numbers are: a(n) = f(n,n,n).

a(3)> 2^(76*2^(76*2^(76*2^(76*2^76)))) so is too big to be included.

Examples

			a(1) = f(1,1,1) = f(0, f(1,1,0), f(1,1,0)+1) = f(0, 1, 2) = 1+2 = 3.
		

Links

• Wikipedia, Sudan Function, Primitive Recursive, Ackermann function.

Crossrefs

Cf. A189896, A046859, A260003, A260004, A260005, A260006.

Programs

Mathematica

f[z_, x_, y_] := f[z, x, y] =
Piecewise[{{x + y, z == 0}, {x,
    z > 0 && y == 0}, {f[z - 1, f[z, x, y - 1], f[z, x, y - 1] + y],
    z > 0 && y > 0} }];
a[n_] := f[n,n,n]

PARI

f(z,x,y)=if(z,if(y,my(t=f(z,x,y-1)); f(z-1, t, t+y),x),x+y)
a(n)=f(n,n,n) \\ Charles R Greathouse IV, Jul 28 2015