# The TAK function

The TAK function is defined as follows for integers $$\x\$$, $$\y\$$, $$\z\$$:

$$t(x, y, z) = \begin{cases} y, & \text{if x \le y} \\ t(t(x-1,y,z), t(y-1,z,x), t(z-1,x,y)), & \text{otherwise} \end{cases}$$

Since it can be proved that it always terminates and evaluates to the simple function below,

$$t(x, y, z) = \begin{cases} y, & \text{if x \le y} \\ z, & \text{if x > y and y \le z} \\ x, & \text{otherwise} \end{cases}$$

your job is not to just implement the function, but count the number of calls to $$\t\$$ when initially called with the given values of $$\x\$$, $$\y\$$, and $$\z\$$. (As per the standard rules, you don't need to implement $$\t\$$ if there is a formula for this value.)

You may assume that the three input values are nonnegative integers.

Note that the task is slightly different from the definition of the function $$\T\$$ (the number of "otherwise" branches taken) on the Mathworld page.

Standard rules apply. The shortest code in bytes wins.

## Test cases

(x, y, z) -> output

(0, 0, 1) -> 1
(1, 0, 2) -> 5
(2, 0, 3) -> 17
(3, 0, 4) -> 57
(4, 0, 5) -> 213
(5, 0, 6) -> 893

(1, 0, 0) -> 5
(2, 0, 0) -> 9
(2, 1, 0) -> 9
(3, 0, 0) -> 13
(3, 1, 0) -> 29
(3, 2, 0) -> 17
(4, 0, 0) -> 17
(4, 1, 0) -> 89
(4, 2, 0) -> 53
(4, 3, 0) -> 57
(5, 0, 0) -> 21
(5, 1, 0) -> 305
(5, 2, 0) -> 149
(5, 3, 0) -> 209
(5, 4, 0) -> 213


Python implementation was used to generate the test cases.

• So far I've noticed that (using this question's definition of T rather than that of the linked article) T(x+1,y+1,z+1)=T(x,y,z) and also T(x,y,z)=T(y,z,x) if x>y and y>>z, but I haven't been able to come up with anything more general.
– Neil
Commented Jan 27 at 8:35

# JavaScript (ES6), 73 bytes

Using a single recursive function

Expects (x, y, z).

f=(x,y,z,w)=>x>(r=y)?f(x-1,y,z)+f(y-1,z,x,w=r)+f(z-1,x,y,z=r)-~f(w,z,r):1


Try it online!

### Commented

f = (                     // f is a recursive function taking:
x, y, z,                //   (x, y, z) = input integers
w                       //   w = local variable
) =>                      //
x > (r = y) ?             // save y in the global r; if x is greater than y:
f(x - 1, y, z) +        //   process the 1st recursive call
f(y - 1, z, x, w = r) + //   save r in w and process the 2nd recursive call
f(z - 1, x, y, z = r) - //   save r in z and process the 3rd recursive call
~f(w, z, r)             //   last recursive call, using the previous results
:                         // else:
1                       //   stop and return 1


# JavaScript (ES6), 76 bytes

Using a wrapper function

Expects [x, y, z].

Simply does exactly what is said on the tin.

a=>(r=0,(t=(x,y,z)=>++r&&x>y?t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)):y)(...a),r)


Try it online!

# Jelly, (22?) 26 bytes

ṙJ_JỊ$ṙ-Ñ€Ñ ‘ɼṛṖṪÇ}ṢƑ? Çṛ®  A full program that accepts a list of three non-negative integers, [x, y, z], and prints the call count. (Or 22 bytes as a monadic Link that accepts the same and accumulates in the register (?) - remove the last line.) Try it online! or see the test suite. ### How? There's probably a clever way to produce the count, but this implements the description from the question. ṙJ_JỊ$ṙ-Ñ€Ñ - Link 1: [x, y, z]
J          - indices {[x, y, z]} -> [1, 2, 3]
ṙ           - {[x, y, z]} rotate left by -> [[y, z, x], [z, x, y], [x, y, z]]
$- last two links as a monad - f([x, y, z]): J - indices {[x, y, z]} -> [1, 2, 3] Ị - insignificant? -> [1, 0, 0] _ - subtract -> [[y-1, z, x], [z-1, x, y], [x-1, y, z]] ṙ- - rotate right -> [[x-1, y, z], [y-1, z, x], [z-1, x, y]] Ñ€ - call Link 2 for each Ñ - call link 2 - ‘ɼṛṖṪÇ}ṢƑ? - Link 2, t: [x, y, z] ɼ - apply to the register and yield: ‘ - increment Ṗ - pop {[x, y, z]} -> [x, y] ṛ - right argument -> [x,y] ? - if... Ƒ - ...condition: is {[x, y]} invariant under?: Ṣ - sort Ṫ - ...then: tail -> y Ç} - ...else: call Link 1 as a monad - f(x, y, z) Çṛ® - Main Link: [x, y, z] Ç - call Link 2 as a monad - t(x, y, z) ® - recall from the register -> count ṛ - right argument -> count  • Ñ calls link 2 from link 1, doesn't it? – Neil Commented Jan 26 at 2:22 • Corrected, thanks! Commented Jan 26 at 2:48 • I don’t think the 22 is valid. It seems akin to storing the result in a variable, and also the monadic link is not reusable since it doesn’t initialise the register. Overall good solution though Commented Jan 26 at 7:37 # Perl 5-Mfeature+signatures -ap, 83 bytes sub f($x,$y,$z){++$;;$y<$x?f(f($x-1,$y,$z),f($y-1,$z,$x),f($z-1,$x,$y)):$y}f@F;$_=$ Try it online! # Python 2, 103 bytes def t(x,y,z):t.c+=1;return t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y))if x>y else y t.c=0 t(*input()) print t.c  Attempt This Online! # Charcoal, 116 bytes ≔⦃⦄θ⊞υＥ³ＮＦυ«≔Ｉ⪫()⪫ι,ηＦ¬§θη¿‹§ι¹§ι⁰«≔ＥιＥι⁻§ι⁺μξ¬ξζ⊞ζＥζ§λ∨¬‹§λ¹§λ⁰⊗¬‹§λ²§λ¹≔Ｅζ§θＩ⪫()⪫λ,ε¿⬤ελ§≔θη⊕ΣεＦ⊞Ｏζι⊞υλ»§≔θη¹»Ｉ§θη  Attempt This Online! Link is to verbose version of code. Explanation: Charcoal isn't really suited for this. ≔⦃⦄θ  Start with an empty dictionary which will hold T(x, y, z) for each required tuple. ⊞υＥ³Ｎ  Start with the input tuple. Ｆυ«  Loop over the required tuples as they are found. ≔Ｉ⪫()⪫ι,η  Convert the tuples from a list to a Python tuple so that they can be used as a dictionary key. Ｆ¬§θη  Test to see whether this tuple's T value is already known. ¿‹§ι¹§ι⁰«  Test to see whether this is a trivial tuple. ≔ＥιＥι⁻§ι⁺μξ¬ξζ  Generate the dependent tuples, (x-1, y, z), (y-1, z, x) and (z-1, x, y). ⊞ζＥζ§λ∨¬‹§λ¹§λ⁰⊗¬‹§λ²§λ¹  Also generate the fourth tuple by calculating t for each of these tuples nonrecursively. ≔Ｅζ§θＩ⪫()⪫λ,ε  Get any T values we have for these tuples already. ¿⬤ελ  If all of these tuples already have T values, then... §≔θη⊕Σε  ... take the sum and set this as the T value for the required tuple. Ｆ⊞Ｏζι⊞υλ  Otherwise push all of the tuples to the list for reprocessing because it's simpler that way. »§≔θη¹  If this is a trivial tuple then just set its T value to 1. »Ｉ§θη  Output the T value of the input tuple. # 05AB1E, 30 bytes "¼Â¦@iÅsë2Ý._εć<š®.V}®.V"©.V¾  Input as a triplet $$\[x,y,z]\$$. Explanation: "..." # Push the recursive string explained below © # Store it in variable ® (without popping) .V # Pop and evaluate it as 05AB1E code ¾ # Push counter variable ¾ # (which is output implicitly as result) ¼ # Increase the counter variable ¾ by 1 (starts at 0 by default) Â # Bifurcate the current triplet; short for Duplicate & Reverse copy # (which will use the implicit input-triplet in the first iteration) ¦ # Remove the first item of the reversed triplet (the z)  # Pop and push y and x separated to the stack @i # Pop both, and if x>=y: Ås # Pop the triplet, and push its middle: y ë # Else: 2Ý # Push list [0,1,2] ._ # Rotate the triplet that many times towards the left: [[x,y,z],[y,z,x],[z,x,y]] ε # Map over each rotated triplet: ć # Extract its head; push remainder-pair and first item separately < # Decrease this first item by 1 š # Prepend it back to the pair ®.V # Do a recursive call by evaluating string ® }®.V # After the map: do a recursive call on the resulting triplet as well  # AWK, 82 bytes func t(x,y,z){$0=++c;return x>y?t(t(x-1,y,z),t(y-1,z,x),t(z-1,x,y)):y}t($1,$2,\$3)1


Attempt This Online!