5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ this is worth a read :) $\endgroup$ – Nic Sep 21 '14 at 6:24
  • $\begingroup$ wow....Its very nice. Thank you bro. $\endgroup$ – Bumblebee Sep 21 '14 at 6:40
  • $\begingroup$ I have no particular interested about $100.$ I want to know more details about the whole constructable number set. $\endgroup$ – Bumblebee Sep 22 '14 at 4:58
  • 1
    $\begingroup$ $(1+2)\times3\times4\times5\times6\times7\times8\times9=544320$ is the largest number. $\endgroup$ – Xoff Sep 22 '14 at 5:26
  • 1
    $\begingroup$ @Nilan No :) You should even be able to prove it with a small proof. $\endgroup$ – Xoff Sep 22 '14 at 6:43
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I had never learn about the dynamical programming. Can you give me a easy reference for that. How did you calculate the smallest non constructible number? $\endgroup$ – Bumblebee Sep 22 '14 at 8:19
  • $\begingroup$ en.wikipedia.org/wiki/Dynamic_programming . For the smallest number, I just compute all the computable numbers and find the smallest not in the list. $\endgroup$ – Xoff Sep 22 '14 at 9:41
  • $\begingroup$ Thank you Xoff. I'll follow this. Thank you very much. $\endgroup$ – Bumblebee Sep 22 '14 at 10:20
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.