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.