The Takeshi Kitano Challenge

Launched in 2011 at the Cartier Foundation, the Takeshi Kitano challenge consists in finding a n-solution (with n as small as possible) allowing to reach a target number (typically the current year number) with an expression in which appear successively, in order, the number from 1 to n separated by mathematical symbols. I haven't found the explicit list of the operators, and have considered the following ones: +, −, ×, ÷ and power for binary operators; −, √ and ! for unary operators.

This page explains the thought process in the writing of a program which solves this problem.

A point of interest relates to the integer or real nature of the computation, and I haven't found an answer to this question. We can suppose that there are little chances that a non-integer intermediate result ends up in an integer final result, but this is theoretically possible. Though, I have only considered integer only computations, i.e. computations in which all the intermediate results are integers.

The first part consists in enumerating all the binary trees for a given number N of leaves (see figure below).


Enumeration of all binary trees for N = 4 (4 leaves)

It is not trivial to obtain every tree a single time by construction, and having not managed to write such an algorithm for now, I simply used a recursive approach consisting in selecting all possible consecutive pairs at a given level (partially constructed tree), and to recursively call the selection on the constructed part, including the newly created node. This approach has a cost in (N−1)!, and there is a need to detect already explored trees, what I did with a textual representation of the tree. Although this may seem inefficient (6 trees instead of 5 for N = 4, 24 trees instead of 14 for N = 5, etc.), the cost for exploring the trees is absolutely negligible in front of the cost for exploring the operators for a given tree. Once a tree is built, we need to explore all the possible combinations of operators before computing its value. If we only consider the binary operators +, −, ×, ÷ and power, there are 5^N−1 configurations for a given tree. For unary operators, those can be combined an arbitrary number of times, what can quickly make the number of combinations explode. Thus, I have only considered some of the combinations and a limited number of times. More particularly, the considered combinations are the following:

• identity
• −
• √
• !
• −∘√
• √∘−
• !∘−
• −∘!

As for the missing combinations, we can list the potentially relevant input values, which we consider to be the ones for which both their values and associated output values are at maximum of the order of magnitude of the target value. Nevertheless, we can note that an intermediate value close to (or higher than) the target value has little chances to appear in an optimal computation of the target.

• !∘! : only the value 3 is relevant
• √∘√ : The values 16, 81, 256, 625, 1296, 2401 are potentially relevant
• !∘√ : The values 9, 16, 25, 36, 49 are relevant
• √∘! : Does not produce any integer until 12 (> 21 886)
• √∘√∘√ : The value 256 is relevant
• −∘!∘− : Could be considered as well as !∘−
• −∘√∘− : Could be considered as well as √∘−

To avoid exploring unwanted combinations, unary operators have been directly combined to form other unary operators. Unary nodes have been added in the tree above each binary node and each leaf. The factorial operator is implemented as an array, but not the square root because of the array size and the resulting cache effects (although from my own experiments, it does not change much the computation time).

If we consider the 8 unary operators obtained, there are 5^N−1×8^2×N−1 combinations. A naive approach then simply consists in enumerating these combinations and compute the tree value.

However, such a naive enumeration poses two problems:

• First, it requires to compute the whole tree at every operator change, even if some intermediate nodes are unchanged (for example, if the modified operator is the root, only that node needs to be re-computed)
• Second, it forces the exploration of a lot of configurations which potentially have, at the root of the exploration tree, an irrelevant computation.

To face these two problems, the idea is to explore the operators starting from the greatest depths first, so as to be able to re-evalute only the current node, and to cut from the exploration tree all the sub-trees when the result of a node gives a non-integer or impossible result (square root of a negative number, for example).
The program, whose code can be found here gives the following results for target numbers 2011 to 2019:

• 2011 = ((((1 + 2) + 3) ^ 4) − 5) + (6!)
• 2012 = −((((1 + 2)!) × (3!)) − sqrt(4 ^ (5 + 6)))
• 2013 = (((1 × 2) + ((3!) ^ 4)) − 5) + (6!)
• 2014 = (((1 + 2) + ((3!) ^ 4)) − 5) + (6!)
• 2015 = −(1 − ((((2 ^ 3)!) / 4) / 5))
• 2016 = (((−((1 − 2) − (3!)))!) × sqrt(4)) / 5
• 2017 = 1 + ((((2 ^ 3)!) / 4) / 5)
• 2018 = −((((1 + 2) − ((3!) ^ 4)) − 5) − (6!))
• 2019 = −((((1 × 2) − ((3!) ^ 4)) − 5) − (6!))

Given these results, it is possible to consider more unary operators, by limiting the search to the sizes strictly less than the found ones (for example N = 5 for 2011). Given that the search for N = 5 is currently very fast, it is possible to consider a lot more unary operators and still have reasonable execution times.