I ran across this puzzle yesterday.

Write a function that, given a positive integer, will express that number as a series of simple mathematical operations (add, subtract, multiply, divide) using only single-digit numbers. Output of the function is a string containing a postfix expression.

So, for example, 36 would result in 66* or 94*. 11 would be 92+ or 74+, etc. The number 101 could be expressed as 554**1+.

It didn’t take long to come up with a recursive function that meets the requirements. Here it is in C#:

    string GetExpression(int val)
    {
        if (val < 10)
        {
            return val.ToString();
        }
        int quo, rem;
        // first see if it's evenly divisible
        for (int i = 9; i > 1; --i)
        {
            quo = Math.DivRem(val, i, out rem);
            if (rem == 0)
            {
                if (val >= 90 || (val < 90 && quo <= 9))
                {
                    // value is (i * quo)
                    return i + GetExpression(quo) + "*";
                }
            }
        }

        quo = Math.DivRem(val, 9, out rem);
        // value is (9 * quo) + rem
        // optimization reduces (9 * 1) to 9
        var s1 = "9" + ((quo == 1) ? string.Empty : GetExpression(quo) + "*");
        var s2 = GetExpression(rem) + "+";
        return s1 + s2;
    }

The overall idea here is that first I try to divide the number evenly by a one-digit number. If it does divide evenly, then the result is (x * quotient), where x is the divisor. If the number isn’t evenly divisible by a one-digit number, then the function divides the value by nine and generates (9 * quotient) + remainder.

I made one simple optimization based on the observation that any number in the range 0-90 inclusive can be expressed either as the product of two single-digit numbers, or with an expression of the form (9 * x) + y, where x and y are one-digit numbers. 31, for example, is (9 * 3) + 4, or 93*4+ in postfix.

The function above generates the shortest possible expressions for all numbers in the range 0 through 90. I think its expressions for 91 through 101 are as short as possible, if non-obvious. But I know that it doesn’t always generate optimum expressions. For example, the generated expression for 10,000 is 85595*5+*** (it works out to (8 * 1250)). But 10,001 results in 99394*5+**4+*2+ (postfix for (9 * 1111) + 2). A shorter expression would be (10000 + 1) or, in postfix, 85595*5+***1+.

I’m at a loss as to how I would go about ensuring an optimum expression for any positive integer. I know that I could add more special cases, but I’m already disappointed by the existing special case in my algorithm for numbers 0 through 90. Even the check for even divisibility kind of bothers me, but that’s the only way I could find to make things reasonable at all.

If the puzzle interests you, I’d be interested in any insights.