Creating arbitrary number from one digit numbers and simple operations

Question

How do I compute an arbitrary integer using the fewest elementary arithmetic operations (add, sub, mult, div) on single digit integers as optimally as possible?

Numbers form 0-9 have 0 cost. Other numbers must be build up form them using elementary operations.

Examples: 25 is build up from 5*5

123 can be build up by many different ways but the most optimal is 5*5*5-2.

At first I wanted to solve it by dynamic programming but I couldn't over come barrier of introducing multiplication and I don't think it is practical for large numbers. But if it is please tell me how to do it.

If someone could direct me to right problem similar to this I would be grateful.

Answer 1

Unfortunately, the answer that you are looking for isn't quite as straightforward as could be for other questions on SO. The consequence being that you were voted down a number of times. I might not have been so quick to pull the trigger on this one, but it is a valid question.

I would suggest that you determine the set of numbers that can be reached with only one arithmetic operation (All integers between -9 and 18 and numbers appearing in a multiplication table), with two arithmetic operations... with three arithmetic operations and so on, such that membership within the solution set for a given number of arithmetic operations can determine the infimum of the statement size for a given target integer x:

{x ϵ I} c A(N);

singleton "x" element of integers is a subset of A(N), where A(N) is defined as the set of possible solutions after performing N possible arithmetic operations. (The supremum(N) defined as the number of arithmetic operations in "1+1+1...+1+1" for positive numbers and "0-1-1...-1-1" for negative numbers)

Then the set of optimal solutions would be defined by:

A( infimum(N) ), where infimum(N) minimizes the number of arithmetic operations.

EDITED: I had done some further roughage about with my pencil this evening and previously I had suggested non-primes as members of A(1), which would be an exception at any non-prime number with a prime factor >= 11. The least of which is 22 as pointed out below.

If we start with A(0) defined as the closed set of integers [0,9] Then A(n+1) = u( A(n), A(0) ), u being the set of arithmetic functions.

Since division cannot be part of an optimal solution, due to the existence of a least common multiple for non-rational results, then u'(x, y) = { x + y, x - y, x * y }; the least restrictive set containing x and y being integer.

The same elimination does not hold for subtraction, because we need the neighborhood above and below the product.

We can eliminate zero from all optimal solutions as well, leaving A'(0) = [1,9]. because we note that singleton {0} ϵ A(0) and since by the definition of zero,

0 * A(n) = 0, and
0 + A(n) = A(n)

The optimal solution for zero is always "0" and since any appearance of "+0+", or zeros within a product space cancelled out the whole product or the zero addition step, the solution is not optimal and thus could be excluded from the search.

So then one way in pseudocode to find the whole solution set for A(n), n ϵ N (naturals), neglecting order of operations would be:

**A**(n) = **A**(n-1); // n*1 is still included, 
                       //  and n+0 is by proxy included for posterity 

for x ϵ **A**(n-1)
    for y ϵ **A'**(0)
        for u ϵ **u'**
            A(n) = Union( A(n), u(x,y) );
        next u
    next y
next x 

Mind you I cannot ascertain whether the output is sorted or not AND we neglected order of operations, so this is not yet a valid, complete algorithm for the solution you are seeking and further I'm nodding off, so I'll edit this again and describe order of operations.

EDITED: Description of Order of Operations

First, thank you for accepting this solution and as I said last night, I would describe order of operations.

Since we are dealing with multiplication specifically, then we ought to find the products within the statement first, such that we would have a set P, that would represent the set of addends and evaluated products buried within an acceptable statement; we will not represent P with a string.

So first we need to traverse the string and look for multiplication operations so we can create an array P of integers whose summation is the solution for the statement. In pseudocode this might look like this:

array **P** = empty    // the upper limit for the bounds of **P**
                       //  is number of operators - number of multiplications + 1

first **P** = first **d**   // we can initialize the first value of **P**

for j ϵ N, j <= n      // j is a natural number and 'n' is the number of operators

    given u(j) ϵ **u** // **u** is the set of operations
    given d(j) ϵ **d** // **d** is the set of digits of length n + 1        

    if u(j) is not multiplication
    {
        **P** = Union( **P**, d(j+1) );   // append d(j+1) to the end of **P**
        if u(j) is subtraction negate last **P**  // then last **P** is negative
    }
    else //---> u(j) is multiplication
    {
        last **P** *= d(j+1)
    }

next j

solution = sum **P**; solution ϵ I. 

Now we have a routine to evaluate the statement in deference to order of operations, that we can call eval. Returning to the previous loop structure, the recursive property optimization breaks down when we respect order of operations.

("2+4*3" = 14 not 18)

So we are stuck with a routine that must search through the set of possible statements for 'n' operations. Then we can narrow the set of statements by eliminating addition and multiplication by zero and further by eliminating multiplications by one, which it appears that you have also done. I'm assuming that the cryptic that you provided checks not only that the previous operation is u ϵ { +, - } before appending a digit '1', but also that the previous digit is not '1' before appending an operation u ϵ { * }.

Once we are able to search through the optimized statement set of a certain length for the target integer we can iterate the length property of statements until the target integer is an evaluated solution, then we can start saving the statements of the minimized length evaluating to the target integer into an array of strings and stop after iterating through the rest of the statements of a given size.

That would be an exhaustive search. Even if we were to check the target integer for divisibility into a product space of digits, what happens when we cannot cleanly break it down into a product space of single digit numbers? Can you propose a number theory optimization, given a set of integers that are represented by a product space of single digit numbers with indeterminate length possessing a mapping that indicates the optimal solution for the space and the number of multiplications in the product space? If not, then we're stuck with the exhaustive search, for now.