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.



Optimal Countdown
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$. 


