3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For $n>2$ $f(n)>2^n.$ Because $2^n = \left(2^1\right)\cdot \left(2^{n-1}\right).$ $\endgroup$ – Thomas Andrews Aug 21 at 20:09
  • $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Aug 21 at 20:12
  • $\begingroup$ "Notice we haven't used multiplication or division yet" -- but we do need multiplication already to arrive at $f(2)\ge 4$ $\endgroup$ – Hagen von Eitzen Aug 21 at 20:13
  • $\begingroup$ @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. $\endgroup$ – Vepir Aug 21 at 20:18
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Hagen von Eitzen Aug 21 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.