TAK Function

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).

Explore with Wolfram|Alpha

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.