A recursive function devised by I. Takeuchi in 1978 (Knuth 1998). For integers , ,
and , it is defined by
|
(1)
|
This can be described more simply by
|
(2)
|
Let be the number of times "otherwise"
is called in the above function. Then for is given by
(Vardi 1991).
The Takeuchi numbers are defined by .
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