|
%I #28 Jan 11 2020 15:57:47
%S 0,3,15569256417
%N Sudan Numbers: a(n)= f(n,n,n) where f is the Sudan function.
%C 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)).
%C The Sudan function is defined as follows:
%C f(0,x,y) = x+y;
%C f(z,x,0) = x;
%C f(z,x,y) = f(z-1, f(z,x,y-1), f(z,x,y-1)+y).
%C 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).
%C a(3)> 2^(76*2^(76*2^(76*2^(76*2^76)))) so is too big to be included.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sudan_function">Sudan Function</a>, <a href="https://en.wikipedia.org/wiki/Primitive_recursive_function">Primitive Recursive</a>, <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.
%e a(1) = f(1,1,1) = f(0, f(1,1,0), f(1,1,0)+1) = f(0, 1, 2) = 1+2 = 3.
%t f[z_, x_, y_] := f[z, x, y] =
%t Piecewise[{{x + y, z == 0}, {x,
%t z > 0 && y == 0}, {f[z - 1, f[z, x, y - 1], f[z, x, y - 1] + y],
%t z > 0 && y > 0} }];
%t a[n_] := f[n,n,n]
%o (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)
%o a(n)=f(n,n,n) \\ _Charles R Greathouse IV_, Jul 28 2015
%Y Cf. A189896, A046859, A260003, A260004, A260005, A260006.
%K nonn,bref
%O 0,2
%A _Natan Arie Consigli_, Jul 12 2015
|
