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

0, 3, 15569256417

Offset

0,2

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.

Links

Table of n, a(n) for n=0..2.

Wikipedia, Sudan Function, Primitive Recursive, Ackermann function.

Example

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

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]

Prog

(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

Crossrefs

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

Sequence in context: A154998 A036236 A235357 * A368723 A058447 A275939

Adjacent sequences: A259999 A260000 A260001 * A260003 A260004 A260005

Keyword

nonn,bref

Author

Natan Arie Consigli, Jul 12 2015

Status

approved