Motivation
Solution to this problem is a lower bound for a more general problem.
Problem
Given first $n$ powers of two: $1,2,4,8,16,\dots,2^{n-1}$ that all need to be used exactly once per number expressed, what is the smallest positive integer $f(n)$ that can't be made, if we can use the four basic arithmetic operations $(+,-,\times,\div)$, and parentheses?
The $f(1)=2$ is trivial, as well as $f(2)=4$, for example given $\{1,2\}$:
$$\begin{array}{} 1 &= 2-1 \\ 2 &= 2\times 1 \\ 3 &= 2+1 \end{array}$$
But we can't make four which is trivial to conclude, so $f(2)=4$.
Progress
It is clearly true $f(n+1)\ge f(n)$ since we can reduce the $n+1$ case to $n$ case by subtracting last two powers. This means that we can rebuild all the numbers from previous case at least. Even more so, we can inductively show that:
- $f(n)\ge2^n$, for all $n\ge1$ by constructing first $2^n-1$ numbers.
But I'm not sure how to extend the construction for more numbers to reach the full $f(n)$.
The solutions so far, along with pattern for $f(n)$:
$$\begin{array}{} n & f(n) & f(n+1)\ge f(n)\ge 2^n \\ 1 & 2 & 2^1 \\ 2 & 4 & 2^2 + 0 \\ 3 & 11 & 2^3 + 0 + 3 \\ 4 & 27 & 2^4 + 0 + 3 + 8\\ 5 & 77 & 2^5 + 0 + 3 + 8 + 34\\ 6 & 597 & 2^6 + 0 + 3 + 8 + 34 + 488\\ 7 & 2473 & 2^7 + 0 + 3 + 8 + 34 + 488 + 1812\\ 8 & 9643 & 2^8 + 0 + 3 + 8 + 34 + 488 + 1812 + 7042 \\ 9 & ? & 2^9 + 0 + 3 + 8 + 34 + 488 + 1812 + 7042 + ?? \end{array}$$
Here is the brute force output for $n=4,5,6$.
Relevant: $A071314$ - Note that there we are allowed to not use all powers per expression, unlike here. Also note that there for some reason $a(6)=595$, meaning they don't allow to build $595$ (see end of this post how we can actually make it). I think there "intermediate fractions" are not allowed, or the sequence terms are incorrect.
Since $f(n+1)\ge f(n)$, notice $f(n+1)=f(n)+g(n)$, $g(n)=0,3,8,34,488,1812,7042,\dots$
Is it possible to find $f(n)$ in terms of $n$ for all $n$?
Can we find $g(n)$ or compute it efficiently?
Are there similar problems with results that can provide insight into this problem?
To clarify the base construction
We can prove first $2^n-1$ numbers can always be constructed inductively. Assume this is true:
- The $2^n-1$ is simply the sum of the powers. The last step is obtainable.
- The $2^{n-1}$ is the last term, and previous case $(n-1)$ can by assumption build all numbers from $1$ to $2^{n-1}-1$. Summing these terms gives us all numbers from $2^{n-1}$ to $2^n-1$. Repeat this for $(n-2)$ and so on until you reach the base case $1$.
- From $n,\dots,1$ we reached the base case $\{1\}$ which trivially builds $1$. We can build all numbers from $1$ to $2^n-1$ which was shown inductively.
This means $f(n)\ge 2^n$ for $n\ge 1$. Notice we haven't used division yet.
Extending the construction
We ca now try to extend the construction: Let $d=2^{n-1}$ largest power.
For $n\ge3$, we can show we can obtain the $3$ extra terms:
$d\cdot 2 \cdot 1,\space d\cdot 2 + 1,\space (d + 1)\cdot 2$
So we have: $f(n)\ge 2^n+3,n\ge 3$, and for this case $f(3)=11$.
For $n\ge4$, we can show we can obtain the $8$ extra terms:
$d\cdot 2 + (4-1),\space d\cdot 2 + (4\cdot1),\space d\cdot 2 + (4+1),\space (d +1)\cdot 2 + 4$,
$\space (d +4)\cdot 2 -1,\space (d +4)\cdot 2 \cdot1,\space (d +4)\cdot 2 +1,\space (d +4+1)\cdot 2$,
So we have: $f(n)\ge 2^n+11,n\ge 4$, and for this case $f(4)=27$.
And so on, for $f(5),f(6),\dots$ we can construct $34,488,\dots$ extra terms. But I do not see a pattern for generally extending $n$ to $n+1$.
Use of division $(\div)$
Also note that these first five values of $f(n)$ can be obtained without the use of division. And the $f(6)$ would be $595$ if division is not allowed, but with division allowed it is $597$, so after $n\ge 6$, the division is significant.
That is, $595$ has only one representation possible (ignoring permutations of it):
$$ 595 = (1 + 16 + 4/8 )\times(2 + 32) $$
Numbers usually tend to have multiple representations.
This is also the one of the only numbers, that require "intermediate fractions", like $4/8$, to be made. The only other such number so far, is $2471$. All but these two numbers can be made without "intermediate fractions", up to and including all $n\le 8$ cases.
