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?

-
I have a feeling that you do need division sometimes. For instance, take numbers like 1+9+81+729+...+9^k. These are easy to make with division: (9*9*9*...*9-1)/8. But I'm not sure how to prove this works; that is, that at least some of these numbers are "rough" enough that there's no more efficient way to make them. –  Lopsy Feb 10 '12 at 2:48
Lopsy: You can calculate with a computer the smallest number of operations required with or without division. That wouldn't constitute a proof for general $n$, but will at least answer the OP's question. –  Yuval Filmus Feb 10 '12 at 5:46
Could you be more precise of what to do if a division is not exact? Either you simply forbid this, or you consider the rational result as a valid intermediate value, or you take the quotient ignoring the remainder. I think your conjecture is false even if you simply forbid inexact divisions, but it helps to have carity about this first. –  Marc van Leeuwen Feb 10 '12 at 12:34
@Marc: I used only exact division for my answer. –  joriki Feb 10 '12 at 13:02
Do you allow parenthesis? eg. (1+9)*9 –  user1708 Feb 10 '12 at 13:19

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

-
Wow really a nice answer, which reflects your hard-work sir. Fantastic answer. –  Iyengar Feb 10 '12 at 13:03
@Iyengar: Thank you! –  joriki Feb 10 '12 at 13:06
+1. Could you add a table with the smallest number not expressible in n operations? –  user1708 Feb 10 '12 at 13:19
@Holowitz: Done. –  joriki Feb 10 '12 at 13:48
Excellent stuff. If you're still keen you could see what happens for negative numbers. –  wxffles Feb 10 '12 at 19:15