I found this puzzle on the ITA
Software web site. It is one of
ITA's "retired" puzzles. The
web site does not give the answer.
I suppose the puzzle is difficult
enough to require writing a program
to solve it. I thought programming
this was quite a little tricky but
fun as well. I have an answer but
bugs have been known to creep into
my code. I hope you enjoy it.
Here it is:
Combining nine 9s with any number of
the operators +, -, *, /, (, ) , what
is the smallest positive integer that
cannot be expressed?
Hints:
1)The answer isn't zero. You can
express zero like this:
(9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
Also, zero isn't a positive integer.
2)The answer isn't one. You can
express one like this:
9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
3)It's not a trick question.
4)Be sure to handle parentheses
correctly.
Notes:
1)You cannot exponentiate.
2)You cannot concatenate (for example,
put two 9s together to make 99).
3)The - operator can be used in either
its binary or unary form.
4)Assume base 10.