Optimal Countdown

Many know the TV game Countdown, whose French version Des chiffres et des lettres has lasted since 1965.

The rules of the count are as follows: you are given natural integers $n_1,\ldots,n_6$ and a target $N$. You are free to employ the four operations $+,\times,-,\div$. You may employ each $n_j$ at most once. You must end with the result $N$.

For mathematicians, a colleague of mine suggests to modify the rule that way: you are given $k\ge1$. You are free to choose $n_1,\ldots,n_k$. Then you must realize the targets $1,2\ldots,N$. How do you choose $n_1,\ldots,n_k$. What is the largest possible $N_k$ ?

Examples:

• $k=1$, nothing much interesting, $N_1=1$
• $k=2$, then $(1,3)$ yields $N_2=4$
• $k=3$, then $(2,3,10)$ yields $N_3=17$. Optimal ?

Edit about the rules. Parentheses are allowed (and useful). Division $a/b$ is possible only when $b$ divides $a$ in the usual sense of integers. You may have negative integers, but it does not help.

-
I don't think the description is right. How do you realize 1,2,3,4 from (1,3)? Since you can employ each number only once, you cannot realize more than two targets. – Emil Jeřábek Apr 8 '11 at 10:33
Regarding the preceeding comment: why not more than two? 3-1=2, 3+1=4, 3*1=3; and also just 3 and 1 (if I understand correctly) But, I have to agree, I do not quite understand the question either: a. does one have parenthesis avalailable, e.g., is (a+b)c admissible (as I saw this game once very briefly I believe so). b. are intermediate results allowed to be negative and/or rational. c. related to b. how is division to be interpreted, say is 7/3 , just the rational, or inadmissible, or maybe 2. [I deleted an earlier comment, almost identical, as I asked something that is actually specified] – user9072 Apr 8 '11 at 11:24
Here is a related (maybe easier) question : fix an integer $k$ and assume $n_1=\ldots=n_k=1$. What is the smallest natural integer $N'_k$ which cannot be obtained from the $n_i$ using the above rules ? Obviously one has $N'_k - 1 \leq N_k$, but of course $N_k$ is likely to grow much faster than $N'_k$. Are there interesting lower/upper bounds on $N'_k$ ? – François Brunault Apr 8 '11 at 19:15
Francois: the example I know is making 24 out of 3,8,3,8 (and you have to use all four numbers). For this one you provably need to leave the world of integers. – Kevin Buzzard Apr 8 '11 at 20:29
Taking $n_i=3^{i-1}$ for $1 \leq i \leq k$ yields the lower bound $N_k \geq (3^k-1)/2$ (since every integer $N \leq (3^k-1)/2$ is a weighted sum of powers of 3). However, I have the impression that the actual growth rate of $N_k$ is much faster (and I don't know how to find an upper bound). – François Brunault Apr 9 '11 at 0:49

We can prove that $\log N_k \sim k \log k$ as follows:

If we want to combine a set of $k$ numbers using the four arithmetic operations, we can think of inputting the numbers (in any order) along with the operations into an RPN calculator. There are $k!$ ways of ordering the numbers, $C_{k-1} = \frac1{k}{2k-2 \choose k-1}$ ways of choosing places to insert the arithmetic operations (without running out of numbers on the stack) and $4^{k-1}$ ways of choosing which of the four operations we will insert at each place, for a grand total of $4^{k-1}\frac{(2k-2)!}{(k-1)!}$ ways of combining $k$ numbers with the four operations. If we are given $k$ numbers and we can work with any subset of them (as in the original formulation of $N_k$), then there are $$\sum_{i=1}^k {k \choose i} 4^{i-1}\frac{(2i-2)!}{(i-1)!} = \sum_{i=1}^k 4^{i-1} C_{i-1} \frac{k!}{(k-i)!} \le 16^k k! \le (16k)^k$$ ways of choosing a subset and then arranging and combining the elements of the subset with the arithmetic operations. Hence $\log N_k \le k(\log k + \log 16)$.

The lower bound is a little bit more interesting. Just by using addition and multiplication, we can prove that $N_{b+r-2} \ge b^r - 1$: We take as our $b + r - 2$ numbers $2, 3, \ldots b-1, 1, b, \ldots b^{r-1}$ (of course we are assuming that $b \ge 2$). Then we can write any positive integer $n < b^r$ as $\sum_{i=0}^{r-1} a_i b^i$, with $0 \le a_i \le b-1$, and then, by collecting the terms with a given "digit" $a_i$, we can write $n$ as a sum of terms of the form $a(b^{i_{a1}} + \ldots + b^{i_{aj_a}})$, where each $a$, $0 \le a \le b-1$, appears at most once. Of course, we can throw out the term with $a=0$, and not write the 1 when $a=1$, so we can write our number with $2, 3, \ldots, b-1, 1, b, \ldots, b^{r-1}$.

If we allow subtraction as well we can use Francois's idea (and the same set of numbers) to show that $N_{b+r-2} \ge ((2b - 1) ^ r - 1)/2$ when $b \ge 2, r \ge 1$.

Even with only addition and multiplication, we obtain (roughly) $N_k \ge (\epsilon k)^{(1-\epsilon) k}$ for $k$ large given $\epsilon > 0$, and hence $\log N_k \ge (1-\epsilon) k \log k$ when $k$ is large given $\epsilon$. So $\log N_k \sim k \log k$.

The next question to ask is whether $N_k^{1/k}/k$ has a limit, and if so, what is is. We have proven that $\limsup N_k^{1/k}/k \le 16$, but we have not even proven that $\liminf N_k^{1/k}/k > -\infty$.

-
Very nice lower bound ! Could you explain in more detail the argument with the Catalan number for the upper bound ? (I had found the crude upper bound $N_k = O(2^k (k!)^2)$, but maybe I wasn't careful enough.) – François Brunault Apr 12 '11 at 17:36
For example, with the numbers 1, 2, 3, and 4, in order, and the operation *, there are five ways that we can enter them into an RPN calculator: 1 2 * 3 * 4 *, 1 2 3 * * 4 *, 1 2 * 3 4 * *, 1 2 3 * 4 * *, and 1 2 3 4 * * *. In general, there must always be more numbers inputted into the calculator than there are operations applied: this condition is what gives us the Catalan numbers. – Jeremy Kahn Apr 14 '11 at 0:31
@Jeremy Kahn: Thanks for the detailed explanation. In fact I used a different argument, but now I realize that your method gives a better upper bound. – François Brunault Apr 14 '11 at 11:20

For convenience, we write $(a_1, \ldots, a_k) \le (b_1, \ldots, b_k)$ when $a_i \le b_i$ for each $i$. When $k = 3$, the solution $(2, 3, 10)$ is optimal among $(n_1, n_2, n_3) \le (10, 20, 100)$. For $k = 4$, you can make $1 \ldots 79$ with $(2, 3, 5, 33)$. This is optimal for $(n_1, n_2, n_3, n_4) \le (2, 4, 6, 50)$. These results were obtained with a perl script I wrote that you can find at www.math.sunysb.edu/~kahn/countdown. The last result, for example, was obtained by running

countdown 2 4 6 50

and took 7 minutes to run on my MacBook Pro.

-
It may be worth noting that these numbers are not unique. For example, (2,3,10), (2,3,14), (2,6,11) and (2,6,13) all give 17. – user11235 Apr 8 '11 at 20:39
(2,3,15,37) gives 84 – user11235 Apr 9 '11 at 11:05
(2, 3, 14, 60) gives 86. This is optimal for $(n_1, n_2, n_3, n_4) \le (5, 10, 20, 100)$. – Jeremy Kahn Apr 9 '11 at 23:20
Up to $k=4$ the best known solutions seem to form a chain : (2,3), (2,3,14) and (2,3,14,60)... – François Brunault Apr 11 '11 at 16:54

The last results I got using my program CEB are: - For k=5, the best solution $(n_1,n_2,n_3,n_4,n_5)$ ≤ (200,200,200,200,200) is (2,3,4,63,152) and we can get all numbers up to $N_5$=450. - For k=6, the best solution $(n_1,n_2,n_3,n_4,n_5,n_6)$ ≤ (10,20,30,40,50,80) is (2,3,24,37,47,66) and we can get all numbers up to $N_6$ = 3398.

-

Gilles Bannay informed me of the following results he has found :

1. For $k=4$, the solution $(2,3,14,60)$ is optimal for $(n_1,n_2,n_3,n_4) \leq (4,8,80,80)$.
2. For $k=5$, the solution $(2,3,4,63,152)$ gives all numbers up to $450$.
3. For $k=6$, the solution $(2,3,3,11,136,180)$ gives all numbers up to $2003$.
4. Using the original rules from the French TV game, the $6$-tuple $(1,2,3,4,10,100)$ gives all numbers up to $1281$ (which answers my question in a comment).

He obtained these results using his program CEB, which can be downloaded here (the page is in English and contains a detailed explanation of all the options). He has added an option in order to search for the best $k$-tuples. For example, the result 1. above was found by typing :

> CEB -g -b1 -e10000 -a4 4 8 80 80

-
Using Gilles Bannay's program, it took only approximately 3 minutes (!) to test all $6$-tuples $(n_1,\ldots,n_6)$ with $n_i \in \{1,2,3,4,5,6,7,8,9,10,25,50,75,100\}$. The best $6$-tuple is $(2,3,5,8,9,100)$, for which $N_6=1912$. – François Brunault Apr 13 '11 at 14:37