TOPICS
Search

TAK Function

A recursive function devised by I. Takeuchi in 1978 (Knuth 1998). For integers x, y, and z, it is defined by

t(x,y,z)={y for x<=y; t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)) otherwise
(1)

This can be described more simply by

t(x,y,z)={y if x<=y; {z if y<=z; x otherwise otherwise
(2)

Let T(x,y,z) be the number of times "otherwise" is called in the above function. Then T(a,b,0) for a>b>0 is given by

T(a,b,0)=4sum_(k=0)^(b)(a-b)/(a+b-2k)(a+b-2k; b-k)-3
(3)
=1+4sum_(k=0)^(b-1)(a-b)/(a+b-2k)(a+b-2k; b-k)
(4)

(Vardi 1991).

The Takeuchi numbers are defined by T_n=T(n,0,n+1).

The TAK function is also connected with the ballot problem (Vardi 1991).

See also

Ackermann Function, Ballot Problem, Recursive Function, Takeuchi Number, Takeuchi-Prellberg Constant

Explore with Wolfram|Alpha

References

Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, p. 321, 2003.Gabriel, R. P. Performance and Implementation of Lisp Systems. Cambridge, MA: MIT Press, 1985.Knuth, D. E. "Textbook Examples of Recursion." Artificial Intelligence and Mathematical Theory of Computation, Papers in Honor of John McCarthy (Ed. V. Lifschitz). Boston, MA: Academic Press, pp. 207-229, 1990.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Vardi, I. "The Running Time of TAK." Ch. 9 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 179-199, 1991.

Referenced on Wolfram|Alpha

TAK Function

Cite this as:

Weisstein, Eric W. "TAK Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TAKFunction.html

Subject classifications