The puzzle consists of selecting one handful of digits and another handful of binary operation or rules by which the numbers can be combined. The question is then how many different numbers can you generate? Typically the numbers are restricted to being integers only, and often only positive integers are allowed. The permissible operators range from arithemetic operators and bracketing, through to exponentiation, recurring decimals, square roots etc. The particular puzzle I want to solve though is the following:
Combining nine 9's with any number of the operators +, -, *, /, (, ), what is the smallest positive integer that cannot be expressed? You cannot concatenate (for example, put two 9s together to make 99). The minus operator can be used in either its binary or unary form.
This kind of puzzle is periodically under discussion on newsgroups like rec.puzzles and sometimes even mistakenly propogated to sci.math and other related discussion groups.
This class of puzzle is fun to do by hand and it can be quite rewarding to discover a new valid expression for a new integer you haven't found before. It took me 10 minutes to generate expressions for the first 20 natural numbers for the above puzzle.
To answer the puzzle though you need to generate all possible expressions involving the nine 9's with every combination of operators bracketed in every possible way and then find the first natural number not represented. That is, unless you have some deeper insight on what can/can't be represented than I do. And thus we step into the domain of computer programming ...
If you are able to solve this problem without the aid of computers I would dearly like to know how you did it. From this point forward I am going to assume that the problem is only amenable to a computer solution.
Here are some of the questions you will need to answer before you can write a program to solve the problem:
- How are you going to handle bracketing? The number of binary bracketings grows very quickly. This probem is known as 'Catalan Problem'. The number of bracketings is C(2n,n)/(n+1).
- How to incorporate the unary minus?
- Intermediate calculations may be rational, not integer. How are you going to cater for the case of intermediate rational expressions that eventually become integer again after further expansion of the expression?
- How to display/output each bracketed expression?
Many thanks goes to Dave Rusin for supplying me with an elegant algorithm that gets around the potential nightmare associating with a 'Catalanche' of bracketing. The solution involves recursively defining a sequence of expression sets. Here's the algorithm:
Define recursively the sets S_i by S_1 := {9} S_n := Union of sets ( S_i % S_{n-i} ) for i=1 to n-1, where A := S_i B := S_{n-i} A%B = Union of A+B, A-B, A*C, A/D, where A+B = Set of all a+b for a in A, b in B A*B = Set of all a*b for a in A, b in B A-B = Set of all a-b for a in A, b in B A/B = Set of all a/b for a in A, b in B\{0}To see how the algorithm works it is instructive to generate the first couple of iterations by hand. Thus for n=2 we have
S2 = ∪ (S1 % S1) = ∪ ({9} % {9}) = {9+9, 9-9, 9*9, 9/9} = {18, 0, 81, 1} = {0, 1, 18, 81}
Tackling n=3 gives
S3 = (S1%S2) ∪ (S2%S1) = ( {9} % {0, 1, 18, 81} ) ∪ ( {0, 1, 18, 81} % {9} ). Thus
S3 = {9+0, 9+1, 9+18, 9+81, 9-0, 9-1, 9-18, 9-81, 9*0, 9*1, 9*18, 9*81, 9/1, 9/18, 9/81} ∪ (S2%S1). Thus
S3 = {9, 10, 27, 90, 8, -9, -72, 0, 162, 729, 1/2, 1/9} ∪ (S2%S1)That's as much hand calculation as I'd like to do. I'm sure you get the idea.
At this point we have all we need to implement a solution. Some of you may be fortunate enough to have the use of a symbolic algebra package like Maple or Mathematica. I'm not so fortunate but I was able to code up a solution in C/C++. Here is the source code. The nonnegative solutions are listed here. You can download the zip pack that also includes the executable too for those who don't have a C/C++ compiler and trust my code not to do anything bad to their system.
Note that in the implementation I used floating point as a crude way to handle intermediately generated rationals. By careful use of a small number epsilon called e in the program I was able to get back to integers at the end.
The other point worth mentioning is the recursion and bracketing. See how naturally the recursion takes care of the bracketing for us. At each point where an operation is performed a pair of brackets is slapped around the operands. The recursion handles the hard part of generating every possible bracketing.
The program is not fast, taking approximately 10 minutes on a P2 450 MHz machine. Taking the number of 9's to 10 or more will take a long time to run. Memory is the other consideration.
Finally, as you can see from the output there are 4768 positive integers generated. The first five integer gaps being at 195, 201, 211, 229, 230. Thus the first positive integer that cannot be expressed is 195. It would have taken a long time to determine this fact by hand calculation methods.