Four fours is a math puzzle whose goal is to build numbers out of mathematical expressions using four fours, and a restricted set of mathematical operations and symbols.
Problem
I'm interested in the following variation:
Only allowed operations are: $+, -, \times, \div, b^a,\sqrt[a]{b}$ and parentheses $(\square)$.
That is, addition, subtraction, multiplication, division, exponentiation, roots.Exactly four digits $\{d_1,d_2,d_3,d_4\}\in\mathbb N^4$ must be used in every expression.
What is the optimal set of such quadruplet of digits, such that all numbers from $1$ to $N$ can be made, where $N$ is maximized? (What is the maximal $N$ we can achieve?)
Note that by "digit" I mean any natural number - we are not restricted by base ten.
Note that the root requires the degree to be specified.
My conjectured solution is: maximal $N=70$ achieved using optimal set $\{2,3,6,22\}$.
Example
For example, if we were to use the four fours $\{4,4,4,4\}$, the best we can do is $N=9$.
To complete the example, two of such solution lists:
$$\begin{array}{} 1 &= (4 + 4 - 4) \div 4 &= 4^4\div4^4\\ 2 &= 4 - ((4 + 4) \div 4) &= (4\times4)\div(4+4) \\ 3 &= (4 + 4 + 4) \div 4 &= (4\times 4-4)\div 4\\ 4 &= ((4 - 4) \times 4) + 4 &= {4}^{{(4\div4)}^4}\\ 5 &= (4 ^ {4 - 4}) + 4 &= ((4 \div 4) ^ {4})+4\\ 6 &= ((4 + 4) \div 4) + 4 &= \sqrt[4]{4\times4}+4\\ 7 &= 4 - (4\div4 - 4) &= (4 + 4) - (4 \div 4)\\ 8 &= (4 + 4 + 4) - 4&= \sqrt[4]{4^4}+4\\ 9 &= (4\div4 + 4) + 4 &= 4 + 4 + 4\div4 \end{array}$$
You can't make $10$ using this set of digits and the allowed operations.
This would be possible if either concatenation was allowed, or if root was allowed to be used as a unary square root operator, for example:
$$ 10 = (44 − 4) \div 4 = (4 \div \sqrt4) + (4 \times \sqrt4) $$
But this is not allowed in this variation.
Note that the square root is allowed to be used if the degree is specified, since the root operator $\sqrt[a]{b}$ is allowed. For example, we can use $\{2,4,4,4\}$ digits to make $10$:
$$ 10 = \sqrt[2]{4}+4+4 $$
Instead, and improve our $N$ from $9$ to at least $10$.
Brute force approach
WLOG we can assume $d_1\le d_2 \le d_3 \le d_4$.
I've started an exhaustive search to check all digit sets $\{d_1,d_2,d_3,d_4\}$ where $d_4=D$.
Since $D$ is fixed, we can find with brute force the best achievable $N$ in that scenario. By checking all $D\le D_0$ digit cases, we can find the best $N$ under condition that the digits don't exceed $D_0$.
We can also keep track of individual $D$ case records:
$$\begin{array}{} D & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ N & 4 & 12 & 36 & 36 & 46 & 51 & 53 & 51 & 53 & 51 & 51 & 50 & 46 & 51 & 54 \end{array}$$
If we restrict the problem to base $10$, that is $D_0=9$, we have two optimal solutions:
Optimal sets that can reach $N=53$ are $\{1,4,6,7\}$ and $\{2,3,8,9\}$.
Example list of solutions for these can be seen here $\{1,4,6,7\}$ and here $\{2,3,8,9\}$.
I computed this further. Here are individual $N$ records for given $D$ so far:
$$\begin{array}{} D & N & \{d_1,d_2,d_3,d_4\} \\ 15 & 54 & \{2, 3, 6, 15\} \\ 16 & 57 & \{2, 3, 3, 16\}\\ 17 & 57 & \{2, 3, 6, 17\}\\ 18 & 57 & \{1, 3, 8, 18\}\\ 19 & 67 & \{2, 3, 6, 19\}\\ 20 & 57 & \{1, 2, 6, 20\}\\ 21 & 60 & \{2, 2, 3, 21\}\\ 22 & 70 & \{2, 3, 6, 22\}\\ 23 & 60 & \{1, 2, 5, 23\}\\ 24 & 61 & \{1, 2, 5, 24\}\\ 25 & 65 & \{1, 2, 5, 25\}\\ 26 & 66 & \{1, 2, 5, 26\}\\ 27 & 50 & \{1, 2, 6, 27\}\\ 28 & 52 & \{1, 2, 11, 28\}\\ 29 & 54 & \{1, 2, 6, 29\}\\ 30 & 54 & \{1, 2, 8, 30\}\\ 31 & 55 & \{1, 2, 9, 31\}\\ 32 & 57 & \{1, 2, 9, 32\}\\ \end{array}$$
The best being $D=22$ with $N=70$, so far. For this record:
Here are all ways to write down numbers $N=1,\dots,70$, where the root operation is noted as r: (2,3,6,22).txt. There is only one way to make a four - how interesting.
Also notice the pattern of $d_1,d_2=1,2$ after the latest record. The $d_1=1$ is not surprising since $1$ is very useful. For example, dumping excess digits into exponent $1^x$.
I continued the brute force search up to $D=144$ but for a restricted set of digits: $\{d_1=1,d_2\le 10,d_3,d_4\}$, and collected the maximal $N$ for individual $d_4=D$ cases:
Notice there is a sharp decline after $D=52$. This could be either because $d_1,d_2$ restriction, but more likely, because a large $d_4$ is likely worse since the digit set will have harder time producing smaller values.
Proving the maximal $N$?
Can we prove or disprove (improve) the fact that $N=70$ seems to be the best we can do, making $\{2,3,6,22\}$ the optimal digit set?
I think improving it is unlikely given the $(D,N)=(x,y)$ plot above.
Could we prove that if $D$ is large enough, there always exists $N_0\le N_{\text{max}}$ that can't be made?
If we also show, $N_{\text{max}}\le 70$, we have solved the problem.
For $D\ge 53$, $N_0$ seems to always be $\le 30$ so far (given restrictions on $d_1,d_2$).
Perhaps we can partially solve this (solve certain cases).
A trivial example is that if we use $\{1,1,1,D\}$ we can always get at least $N=3$. And by exhausting all subcases of this case, one can see that $N=4$ is impossible for $D\gt 17$, except for values $d=25,64$.
This gives $N_0=N_{\text{max}}=4$ for $D\gt 17, D\ne 25,64$ for $\{1,1,1,D\}$ case of digits.
Upper bound
Maximal $N$ in general surely has an upper bound. A trivial one would be:
$$ N\lt \binom{4}{2}\binom{3}{2}\binom{2}{2}(6\cdot2)^3 = 31104 $$
Which gives the upper bound on the number of distinct values we can make using four numbers and six binary operations (assuming operations are not commutative). We are choosing two numbers at a time to apply an operation to, and out of those three operations applied, each can be one of six and be either applied as $a,b$ or $b,a$ since we are not assuming commutativity.
If we take into consideration we are only after consecutive positive integers and using specifically the six given operations, this bound can be made much much lower - but I do not think it can be made as low as $70$ to solve the problem - so I haven't tried optimizing it, yet.
Simpler case of the problem
If only four basic arithmetic operations were allowed, $+,-,\times,\div$, (removing the exponentiation and roots from the problem) then the conjectured solution is $N=52$ for $\{2,3,4,22\}$.
The only significant records in this case are $N=43,51,52$ for $D=6,8,22$, where $D$ was fully checked up to $64$, and these values can be seen below:
