Constructing numbers from basic arithmetic on digits

I was tooling around over on stackoverflow and happened upon this question. To summarise, given the set of digits $\{1,2,3,4,5,6,7,8,9\}$ and a set of basic arithmetic (binary) operators $\{+,-,\times,/\}$, what is the least number of operations you need to construct a given integer? For example $239 = 8\times6\times5-1$, requires 3 operations.

My conjecture is that division doesn't help you. There is no number that can be constructed using division, that can't be constructed without division using the same number operations (or fewer). Can anyone prove or disprove this?

Solution 1:

Division does help, but you have to use seven operations (eight operands) to find a case where it does. Here's a list of all expressions with seven operations with values that can't be obtained with seven operations without division:

$$ \begin{eqnarray} (5\cdot7\cdot7\cdot9\cdot9\cdot9-1)/2&=&89302\\ (5\cdot7\cdot7\cdot9\cdot9\cdot9+1)/2&=&89303\\ (7\cdot7\cdot7\cdot9\cdot9\cdot9-5)/2&=&125021\\ (7\cdot7\cdot7\cdot9\cdot9\cdot9+5)/2&=&125026\\ (7\cdot7\cdot9\cdot9\cdot9\cdot9-3)/2&=&160743\\ (7\cdot7\cdot9\cdot9\cdot9\cdot9+5)/2&=&160747\\ (7\cdot9\cdot9\cdot9\cdot9\cdot9-1)/2&=&206671\\ (7\cdot9\cdot9\cdot9\cdot9\cdot9+3)/2&=&206673\\ (7\cdot9\cdot9\cdot9\cdot9\cdot9+5)/2&=&206674\\ (9\cdot9\cdot9\cdot9\cdot9\cdot9-7)/2&=&265717\\ (9\cdot9\cdot9\cdot9\cdot9\cdot9-5)/2&=&265718 \end{eqnarray} $$

Here's the code I used to find them.

So Lopsy's idea turns out to be a good one. In fact I found the penultimate example, $(9\cdot9\cdot9\cdot9\cdot9\cdot9-7)/2=265717$ with a lot less computational effort than the others by factorizing the numbers of the form $(9^6\pm d)/2$, where $d$ is a single-digit number, finding that $(9^6-7)/2=265717$ is a prime and thus can't be the result of a multiplication, noting that a number this large requires a product with at least six factors and could thus only be formed as $p_7\pm p_1$, $p_6\pm p_1\pm p_1$ or $p_6\pm p_2$ (where $p_k$ is a product of $k$ factors), and checking that no such expression yields $265717$.

Here's an attempt at explaining that all the counterexamples involve division by $2$. The number should be large, in order to require most of the operations to be multiplications and to leave as little room as possible for additions, subtractions and small factors. The divisor cannot divide any of the other numbers, since then it would have to divide both terms and thus could be canceled. Thus, if the divisor were $3$, there could be no factors of $9$, which lowers the attainable maximum to $(8^6+8)/3=87384$, which is below the smallest counterexample. The higher the divisor $d$, the fewer potential candidates there are, since only every $d$-th number is divisible by $d$, and also the lower the attainable maximum. For $d=4$, the value of $(9^6+7)/4=132862$ is still within the lower range of the actual counterexamples, but with only half as many candidates for counterexamples, it may be just a coincidence that there aren't any. For $d=5$, the maximum $(9^6+9)/5=106290$ is already at the lower end of the range, and with only $2/5$ as many candidates, counterexamples aren't to be expected. Since $d=6$ is excluded for the same reason as $d=3$, the next possibility is $7$. For $d=7$, the maximum $(9^6+6)/7=75921$ is already below the smallest counterexample.

Here's a table showing the number $a_n$ of values expressible with $n$ operations (excluding division) and, as requested in a comment, the least value $b_n$ not expressible with $n$ operations:

$$ \begin{array}{c|c} n&0&1&2&3&4&5&6&7\\ \hline a_n&9&39&155&739&3667&16947&77860&379072\\ b_n&10&19&92&417&851&4237&14771&73237 \end{array} $$

The growth rate appears to be well below $9$. That shows that it would be quite wrong to model the expressions as having random values uniformly distributed over the accessible interval $[1,9^{n+1}]$ (where $n$ is the number of operations). The generating function for the number of expressions with $n$ operations (excluding division) approximately satisfies

$$f(x)=9+\frac32xf(x)^2$$

(approximately because the symmetry factor $\frac12$ shouldn't be applied when combining two identical expressions), and the solution is

$$f(x)=\frac{1-\sqrt{1-54x}}{3x}$$

with a singularity at $x=1/54$, so the growth rate of the number of expressions is $54$. If their values were uniformly distributed, the probability for a value not to be represented by an expression would be roughly of the order

$$\left(1-\frac1{9^n}\right)^{54^n}\approx\mathrm e^{-6^n}\;,$$

so we would expect almost complete coverage, i.e. a growth rate of $9$.