I have found all 3,020 expressions satisfying the given restrictions along with four others:
- The digits 1-9 must be in order.
- You are not allowed to take the square root of $1$ or $0$. Without this restriction we could have arbitrarily complex expressions.
- Every subexpression must have a rational value. This excludes expressions that involve terms like $\log[2]\sqrt{2}=\frac{1}{2}$. Without this restriction we could have arbitrarily complex expressions.
- Decimal points are not allowed, since it is not clear how we are allowed to use them.
My algorithm works as follows. I compute a table of values $\mathtt{terms}$, where each element $\mathtt{terms}[i,j]$ represents the possible values of a subexpression starting at the $i$-th number and spanning $j$ numbers. As an example, take the expression:
$$((1 - (2 \times (3 - 4) + 5)) + 6) \times 7 \times 8 \times 9$$
The term $3-4$ is associated with $\mathtt{terms}[3,2]$, and the term $7 \times 8 \times 9$ is associated with $\mathtt{terms}[7,3]$. The entire expression is associated with $\mathtt{terms}[1,9]$, and the individual numbers are associated with $\mathtt{terms}[*,1]$
Each $\mathtt{terms}[i,j]$ is a list of key-value pairs: the keys are the values of that subexpression, and the values are the ways of reaching that value. For example:
$$
\begin{align}
\mathtt{terms}[1, 2] = \{\quad
3 &\to \{1+2\ (1)\},\\
-1 &\to \{1-2\ (1)\}, \\
2 &\to \{1 \times 2\ (1)\}, \\
\tfrac{1}{2} &\to \{1 \div 2\ (1)\}
\quad\}
\end{align}
$$
A quick note: for binary operators (all of them except the square root) I store the operator, the left and right-hand operands, and the size of the left operand. The last one is necessary in the second part of the algorithm, and above and below it is shown in parenthesis. Another example:
$$
\begin{align}
\mathtt{terms}[1, 3] = \{\quad
6 &\to \{1+5\ (1),\ 1\times 6\ (1),\ 3+3\ (2),\ 2\times 3\ (2)\},\\
0 &\to \{1+(-1)\ (1),\ 3-3\ (2),\ \sqrt{0}\},\\
1 &\to \{3\div 3\ (2),\ \log[3](3)\ (2),\ \sqrt{1}\}, \\
\vdots
\end{align}
$$
A few notes:
- For all operators, only the values of the operands are stored instead of the entire subexpressions. This is what makes this method efficient.
- Square roots do not need a length stored with them, since they apply to a single subexpression.
- The restriction on square roots of $0$ and $1$ is not applied at this stage (they add at most a constant overhead).
The algorithm that computes $\mathtt{terms}$ is as follows:
- Loop over $\ell=1\ldots 9$:
- Loop over $i=1\ldots 10 - \ell$:
- If $\ell = 1$, initialize $\mathtt{vals}=\{i \to \{i\}\}$.
- Otherwise, initialize $\mathtt{vals}=\{\}$ and loop through $k=1\ldots \ell-1$:
- Get the possible values of the left-hand and right-hand operands. These are: $$\begin{align}\mathtt{LHS}&=\mathtt{terms}[i,k] \\ \mathtt{RHS}&=\mathtt{terms}[i+k,\ell-k]\end{align}$$
- Construct all possible terms: $$a\circ b\ (k);\ a\in\mathtt{LHS},\ b\in\mathtt{RHS},\ \circ\in\{+,-,\times,\div,\log\}$$
- Add to $\mathtt{vals}$ all terms that result in a rational value.
- Repeatedly take a the square root of each term in $\mathtt{vals}$. If the result is a rational value, add it to $\mathtt{vals}$.
- Set $\mathtt{term}[i,\ell]=\mathtt{vals}$.
Next we traverse $\mathtt{terms}$ in reverse order. Starting with $\mathtt{terms}[1,9]$ we get all the ways to make $2016$, then recursively get all the ways to make each subexpression, ignoring $\sqrt{1}$ and $\sqrt{0}$. This results in a list of 32,282 expressions. I then normalize the expressions using the following transformations:
$$
\begin{align}
\cdots+(x_1+\cdots+x_n)+\cdots &\to \cdots+x_1+\cdots+x_n+\cdots \\
\cdots\times(x_1\times\cdots\times x_n)\times\cdots &\to \cdots\times x_1\times\cdots\times x_n\times\cdots \\
\cdots+(x-y)+\cdots &\to ((\cdots+x)-y)+\cdots \\
\cdots\times(x\div y)\times\cdots &\to ((\cdots\times x)\div y)\times\cdots
\end{align}
$$
This prevent us from counting expressions like $(1+2)+3$ and $1+(2+3)$ as different. After this step, there are only 3,020 distinct expressions. The full list is available here. Note that this list uses Mathematica notation: $\times\to\mathtt{*},$ $\div\to\mathtt{/},$ $\sqrt{x}\to\mathtt{Sqrt[}x\mathtt{]},$ and $\log[b](x)\to\mathtt{Log[}b\mathtt{,}x\mathtt{]}$.
Of particular note are the expressions:
(1+Log[2,Log[3,4+5]])*6*7*8*Sqrt[9]
(1+Log[2,Log[3,4+5]+6])*7*8*9
(i.e:)
$$
(1+\log[2](\log[3](4+5)))\times 6\times 7\times 8\times\sqrt{9} \\
(1+\log[2](\log[3](4+5)+6))\times 7\times 8\times 9
$$
Each of which use $\log$ twice, with two different bases!
