The nine 9's...

    A fellow by the name of ViolenceJack on an mIRC #math channel posed the following question to me on 12/24/2001

Using exactly nine 9s and the operations +, -, *, /, what is the least positive integer not representable? You can use parentheses, but not concatenation (i.e. 99, 999). And finally, all intermediate evaluations must be integers; for example 9*((9/9)/9) isn't allowed because that's the same as 9*(1/9) and (1/9) doesn't evaluate to an integer.

For Example: 1 = (9*9+9-9+9-9+9)/9-9

Try for yourself before seeing the answer below!

Perhaps you can find a logical solution. After fiddling with the expressions for about 10 minutes I decided to just write a program to solve it (only took about 45 minutes to write, 171 lines of C/C++). The following is a list of all representations below the answer, followed by some interesting tidbits found by changing the program parameters slightly: 

0 = (9+9+9+9-9-9-9-9)*9
1 = (9*9+9-9+9-9+9)/9-9
2 = (9+9+9+9+9-9-9-9)/9
3 = (9*9-9-9-9-9-9-9)/9
4 = (9+9+9+9+9+9-9-9)/9
5 = 9-9/9-9/9-9/9-9/9
6 = 9-9/9-9/9+9-9/9-9
7 = 9+9+9-9-9-9/9-9/9
8 = 9+9+9+9-9-9-9-9/9
9 = 9+9+9+9+9-9-9-9-9
10 = 9/9+9-9+9-9+9-9+9
11 = 9/9+9/9+9/9+9-9/9
12 = 9/9+9/9+9/9+9-9+9
13 = 9/9+9/9+9/9+9/9+9
14 = (9+9+9+9+9+9-9)/9+9
15 = (9*9+9+9+9+9+9+9)/9
16 = (9+9+9+9+9+9+9)/9+9
17 = (9*9-9)/9+9+9+9-9-9
18 = 9*9-9-9-9-9-9-9-9
19 = (9*9+9)/9+9+9+9-9-9
20 = (9+9+9+9-9-9)/9+9+9
21 = (9*9+9+9+9)/9+9+9-9
22 = (9+9+9+9+9-9)/9+9+9
23 = (9*9+9+9+9+9+9)/9+9
24 = 9-9/9-9/9+9+9-9/9
25 = 9+9+9+9-9-9/9-9/9
26 = 9+9+9+9+9-9-9-9/9
27 = 9+9+9+9+9+9-9-9-9
28 = 9/9+9-9+9-9+9+9+9
29 = 9/9+9/9+9-9+9+9+9
30 = 9/9+9/9+9/9+9+9+9
31 = (9*9+9+9+9+9)/9+9+9
32 = (9+9+9+9+9)/9+9+9+9
33 = (9*9-9-9-9)/9+9+9+9
34 = (9*9-9)/9+9+9+9-9/9
35 = 9*9-9-9-9-9-9-9/9
36 = 9*9-9-9-9-9-9-9+9
37 = 9/9+9*9-9-9-9-9-9
38 = (9+9+9-9)/9+9+9+9+9
39 = (9*9+9+9+9)/9+9+9+9
40 = (9+9+9+9)/9+9+9+9+9
41 = (9*9+9)/(9+9)+9+9+9+9
42 = 9+9+9+9+9-((9+9+9)/9)
43 = 9+9+9+9+9-9/9-9/9
44 = 9+9+9+9+9+9-9-9/9
45 = 9+9+9+9+9+9+9-9-9
46 = 9/9+9-9+9+9+9+9+9
47 = 9/9+9/9+9+9+9+9+9
48 = (9+9+9)/9+9+9+9+9+9
49 = (9*9*9+9-9-9)/(9+9)+9
50 = (9*9*9+9-9+9)/(9+9)+9
51 = 9*9-((9+9+9)/9+9+9+9)
52 = 9*9-9-9-9-9/9-9/9
53 = 9*9+9-9-9-9-9-9/9
54 = 9*9+9-9+9-9-9-9-9
55 = 9/9+9*9+9-9-9-9-9
56 = 9/9+9/9+9*9-9-9-9
57 = (9+9+9)/9+9*9-9-9-9
58 = ((9*9+9+9)*9-9)/(9+9)+9
59 = 9*9-((9+9+9+9)/9+9+9)
60 = (9*9*9-9-9-9)/9-9-9
61 = (9*9*9-9)/9-9-9-9/9
62 = 9+9+9+9+9+9+9-9/9
63 = 9+9+9+9+9+9+9+9-9
64 = 9/9+9+9+9+9+9+9+9
65 = 9/9+(9*9*9+9)/9-9-9
66 = (9*9*9+9+9+9)/9-9-9
67 = 9*9-9-9+(9+9+9+9)/9
68 = (9*9*9-9-9-9-9)/9-9
69 = 9*9-9-9/9-9/9-9/9
70 = 9*9+9-9-9-9/9-9/9
71 = 9*9+9-9+9-9-9-9/9
72 = 9*9+9-9+9-9+9-9-9
73 = 9/9+9*9+9-9+9-9-9
74 = 9*9-9+9/9+9/9+9-9
75 = 9*9-9+9/9+9/9+9/9
76 = (9*9*9-9-9-9-9-9)/9
77 = (9*9*9-9-9-9)/9-9/9
78 = (9*9*9+9-9-9-9-9)/9
79 = (9*9*9+9-9-9)/9-9/9
80 = (9*9*9+9-9+9-9-9)/9
81 = 9+9+9+9+9+9+9+9+9
82 = (9*9*9+9-9+9-9+9)/9
83 = 9*9+(9+9+9+9-9-9)/9
84 = (9*9*9+9-9+9+9+9)/9
85 = 9*9+(9+9+9+9+9-9)/9
86 = (9*9*9+9+9+9+9+9)/9
87 = 9-9/9-9/9+9*9-9/9
88 = 9*9+9-9+9-9/9-9/9
89 = 9*9+9-9+9-9+9-9/9
90 = 9*9+9-9+9-9+9-9+9
91 = 9*9+9/9+9-9+9-9+9
92 = 9/9+9*9+9/9+9-9+9
93 = 9*9+9/9+9/9+9/9+9
94 = (9*9*9+9+9+9+9)/9+9
95 = 9*9+(9+9+9+9+9)/9+9
96 = (9*9*9-9-9-9)/9+9+9
97 = (9*9*9-9)/9+9+9-9/9
98 = (9*9*9+9-9-9)/9+9+9
99 = (9/9+9)*9+9+9+9-9-9
100 = (9*9*9+9-9+9)/9+9+9
101 = 9*9+(9+9+9-9)/9+9+9
102 = (9*9*9+9+9+9)/9+9+9
103 = 9*9+(9+9+9+9)/9+9+9
104 = (9*9*9*9-9)/(9*9-9-9)
105 = 9*9+9+9+9-((9+9+9)/9)
106 = 9*9+9+9+9-9/9-9/9
107 = 9*9+9-9+9+9+9-9/9
108 = 9*9+9-9+9-9+9+9+9
109 = 9*9+9/9+9-9+9+9+9
110 = 9*9+9+9/9+9/9+9+9
111 = 9*9+(9+9+9)/9+9+9+9
112 = 9*9+(9*9*9-9)/(9+9)-9
113 = 9*9+(9*9*9+9)/(9+9)-9
114 = (9/9+9+9)*(9-((9+9+9)/9))
115 = 9*9+9+9+9+9-((9+9)/9)
116 = (9*9*9-9)/9+9+9+9+9
117 = 9*9+9*9-9-9-9-9-9
118 = (9*9*9+9)/9+9+9+9+9
119 = 9*9+(9+9)/9+9+9+9+9
120 = (9/9+9)*((9*9+9+9+9)/9)
121 = ((9+9)/9+9)*(9/9+9/9+9)
122 = 9*9+((9*9+9/9)*9)/(9+9)
123 = (9*9*9+9)/(9-((9+9+9)/9))
124 = ((9+9)*(9*9-9-9)-9-9)/9
125 = 9*9+9+9+9+9+9-9/9
126 = 9*9+9+9+9+9+9+9-9
127 = 9*9+9/9+9+9+9+9+9
128 = (9+9-9/9-9/9)*(9-9/9)
129 = (9/9+9)*((9+9+9)/9+9)+9
130 = 9*9+(9*9*9-9)/(9+9)+9
131 = 9*9+(9*9*9+9)/(9+9)+9
132 = ((9+9)/9+9)*((9+9+9)/9+9)
133 = (9/9+9+9)*(9-9/9-9/9)
134 = 9*9+9*9-9-9-9-9/9
135 = 9*9+9*9+9-9-9-9-9
136 = 9*9+9/9+9*9-9-9-9
137 = (9+9)/9+(9+9)*9-9-9-9

138 is not so expressible.
It requires at least 10 nines: e.g. 9*9+(((9+9)*9+9)*9)/(9+9+9).

Similarly:
Using 8 eights, least is 85.    'Least' here meaning 'least not expressible'.
Using 7 sevens, least is 38.
Using 6 sixes, least is 22.
Using 5 fives, least is 13.
Using 4 fours, least is 10.

Also:
Using 3 nines, least is 1.
Using 4 nines, least is 4.
Using 5 nines, least is 13.
Using 6 nines, least is 22.
Using 7 nines, least is 33.
Using 8 nines, least is 103.
Using 9 nines, least is 138.
Using 10 nines, least is 265.
Using 11 nines, least is 925.
Using 12 nines, least is 1858.
Using 13 nines, least is 3174.

Update: I received an email from David Bagget who informed me this problem came from their careers page. In their problem though, they didn't restrict the results to integers and report the answer in that case is 195. He said "This problem is based on an old Martin Gardner problem (The Four 4s), which can be solved with paper and pencil."
Update #2: Igor Khomyakovwrote his own implementation to analyze this problem and verified the above results (138 & 195). You can download his program here. He carried out his test on the Solaris 2.6 platform.
Update #3: Jeroen Ruttensent in an implementation he put together. You can download his program here.. He mentioned you can do whatever you wanted with his program as long as you kept his name associated with it.
Joe K. Crump | Number Theory Home