Construct numbers using digits $123456789$ and the operations $+,-,×,÷$

Question

From an old book I found the following question.
Use the digits $1,2,3,4,5,6,7,8,9$ and the operations $"+,-,×,÷"$ with $( )$ for construct the result $100.$
During the computations the order of $123456789$ cannot be broken.
For example $$1+2+3+4+5+6+7+(8×9)=100$$ They have given only this example. I have found that $$1×(-2+3+4)+(5×6)+(7×8)+9=100$$ $$(1×2×3)-(4×5)+(6×7)+(8×9)=100$$

It is easy to prove that number of ways of constructing $100$ is finite. But find all possible constructing ways seems like a hard task.

Here I am curious about what are the positive integers constructable using only the previous operations and above sequence. For example $1$ and $10$ are constructable, because $$1+2-3-4+5+6-7-8+9=1$$ $$1×(2+3+4+5-6-7+9)=10.$$

Note that $$1+(2×3×4×5×6×7×8×9)=362881$$ is the largest constructable number (in the above sense). We cannot construct all the numbers between $1$ and $362881.$ For an example we cannot construct $$-2+(2×3×4×5×6×7×8×9)=362878.$$ How many constructable numbers in between $1$ and $362881$?
Without computing can we find all of constructable numbers?
For a given integer $n$ between $1$ and $362881,$ can we determine it is constructable or not?

There are similar questions about the $123456789$ sequence. But they did not answer for my questions.

Answer 1

You can easily decide if a number can be constructed or not using dynamic programming. For your example, the smallest positive number not constructible is 3683 (and the second one is 3802).

You can compute the numbers you can build from the set $[i,...,j]$ by :

• if $i=j$ : either $i$ or $-i$
• else : for any $i\le k\le j-1$ and any number $a\in[i,...,k]$ and $b\in[k+1,...,j]$ you can compute $a+b$, $a\times b$, $\frac{a}{b}$ (if $b$ divides $a$), and their negation.

Then consider $[1,...,9]$.

You will see that $34625$ different numbers can be computed like that (half are negative).

Answer 2

For the $100$ part, $$ 1-2+(3\times 4\times5)-6+(7\times 8)-9=100. $$