# Calculate constant using minimum number of operations on single digit constants

I have a machine that supports the arithmetic operations plus, minus (unary and binary), multiply, divide and exponent and can load single digit integer constants. Arithmetic operations are performed using floating-point, e.g., 3/2 returns 1.5.

Given an integer constant, X, is there an efficient algorithm that will return an expression containing the minimum number of operators needed to calculate this value?

For instance, the constant 123 can be calculated using three operators as (2+9)^2+2, but there is a two operator solution 5^3-2.

I have a blog post providing more background and some numbers.

-
Disclaimer: I have no idea what I'm talking about. Would that be related to Kolmogorov complexity? – user2468 Mar 31 '12 at 3:41

Of course there is such an algorithm. There is certainly an algorithm using fewer than $X$ operators to calculate $X$ by just doing $1+1+\cdots+1$, so an algorithm could look at all the finitely many expressions using fewer than $X$ operators and pick out one using the fewest operators.

So perhaps what you are really asking is what's the most efficient algorithm for accomplishing the goal, and how efficient is it as a function of $X$. That's likely to be a very hard question. There are unsolved questions about something as simple as "addition chains" (look it up!). There are unsolved questions about how close together exact powers can be. You are asking something far more complicated than either of these problems.

-
I guess efficient was implied, but have edited question to make it explicit. If the problem were restricted to addition it would be trivial to solve (keep adding 9 and on the last addition add the appropriate value). One algorithm is to find the closest value reachable by a power, then recurse finding a solution for the difference between this value and the target value. – Derek Jones Mar 31 '12 at 10:02

You can trivially bound the number by $2\log_2 n$ operations: just use binary number representation and Horner's method. On the other hand, you for some of the inputs you can't do better, i.e. you have to get at least $\Omega(\log_2 n)$ steps, otherwise you won't be able to represent all the numbers. I have no idea if you can do better that something that resembles Dijkstra's algorithm, and the graph will be huge (in each step you can possibly get $5K^2$ new numbers where $K$ is the previous number count).

$$K_1 = \mathrm{O}(1), K_{k+1} = \mathrm{O}(K_{k}^2), K_k = O(K_1^{(2^k)})$$ $$K_{log_2 n} = \mathrm{O}(K_1^n)$$

So this would be like 2-EXP-TIME algorithm (remember the input size is $\log n$). It would be much easier if you wouldn't have division or subtraction, then as the number can only go up, you can disregard anything greater than $n$ (and you could do EXP-TIME by dynamic programming and method similar to change-making algorithm, but right now I don't know if it can or can't be better).

-
Without subtract 101 requires at least four operations, e.g., ((2*7)+9)*4+9, and with subtract can it be done in three, (8+9)*6-1. This is the smallest value that requires a subtract to get a minimum solution. – Derek Jones Mar 31 '12 at 21:36