# Smallest number not expressible using first $n$ powers of $2$ (exactly once each), with $+$, $-$, $\times$, $\div$, and parentheses?

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.

• For $n>2$ $f(n)>2^n.$ Because $2^n = \left(2^1\right)\cdot \left(2^{n-1}\right).$ – Thomas Andrews Aug 21 at 20:09
• I'm not using exponentiation, I am using the product of two of the terms, $2^1=2$ and $2^{n-1}.$ For example, when $n=3,$ $8=2\cdot 4.$ – Thomas Andrews Aug 21 at 20:12
• "Notice we haven't used multiplication or division yet" -- but we do need multiplication already to arrive at $f(2)\ge 4$ – Hagen von Eitzen Aug 21 at 20:13
• @HagenvonEitzen I meant "division", thanks for pointing this out. Multiplication is used only to "glue" the inductive steps for numbers $\lt 2^n$, and only non-trivially significant for constructing larger numbers. – Vepir Aug 21 at 20:18
• All in all the induction step for $f(n)\ge 2^n$ should rather run like this: Assume $f(n-1)\ge 2^{n-1}$. Then to represent $k$ with $1,2,4,\ldots, 2^{n-1}$, we can a) substitute $2^{n-2}$ with $(2^{n-1}-2^{n-2})$ in an $(n-1)$ representation of $k$ if $1\le k\le 2^{n-1}-1$; b) use $2^{n-1}+$ an $(n-1)$ representation of $k-2^{n-1}$ if $2^{n-1}+1\le k\le 2^n-1$; or c) use $2^{n-1}\times$ an $(n-1)$ representation of $1$ if $k=2^{n-1}$. – Hagen von Eitzen Aug 21 at 20:21