

A260002


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


5




OFFSET

0,2


COMMENTS

The Sudan function is the first discovered not primitive recursive function that is still totally recursive like the wellknown threeargument (or twoargument) 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(z1, f(z,x,y1), f(z,x,y1)+y).
Just as the threeargument (or twoargument) 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, y1)); f(z1, 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 * A058447 A275939 A230810
Adjacent sequences: A259999 A260000 A260001 * A260003 A260004 A260005


KEYWORD

nonn,bref,changed


AUTHOR

Natan Arie' Consigli, Jul 12 2015


STATUS

approved



