Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications (Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer-Verlag, 1998). He can be contacted at [email protected].
Our client was a soft spoken, exquisitely dressed Englishman. "I'm on a royal errand," he said. "A young prince of a country that is not my own has asked me to help him with a puzzle. I am only a master of protocol, so I need your help. The problem as I have heard it described is to generate all the whole numbers from 1 to as large a number n as possible using only a single number called a 'generator.' One is allowed, I am told, to use any arithmetic operator — plus, times, minus, and divide — one wants. Parentheses are also allowed. I tell you this last point in the hope that it helps you more than it would help me. Now the goal is to generate all these numbers by using as few generator elements as possible on the average for the numbers between 1 and n. We are not told what the generator is to be and we want the largest n such that the averages can be 5, 6, and 7."
"As I see it, sir," 14-year-old Liane stated with an uncharacteristic politeness, "there are three elements to the problem: the generator k, the average number m of uses of the generator, and the largest number generated n. You give us only m and you want us to find the k that gives the largest generated n such that all numbers from 1 to n can be generated from expressions in k and the number of instances of k on the average is less than or equal to m."
"I think that's it, yes," said the visitor. "I have an economical answer using 4 as the generator and the numbers from 1 to 10. Here they are:
1: 4/4
2: (4+4)/4
3: 4-(4/4)
4: 4
5: (4/4)+4
6: ((4+4)/4)+4
7: (4+4)-(4/4)
8: 4+4
9: (4/4)+(4+4)
10: ((4+4)/4)+(4+4)
"The average number of 4s is 3.1 in this sequence. I'm not sure 4 is the best generator in general, however. Here is the same sequence with 5 as the generator:
1: 5/5
2: (5+5)/5
3: 5-((5+5)/5)
4: 5-(5/5)
5: 5
6: (5/5)+5
7: ((5+5)/5)+5
8: (5+5)-((5+5)/5)
9: (5+5)-(5/5)
10: 5+5
"So, would it be asking too much for you to find, by tomorrow at tea time, the best generator and the highest possible n such that the average number of generators used to form the numbers 1...n is no greater than 5?"
Reader: Liane was able to generate the numbers 1...57 with an average cost of just under 5. Her generator wasn't 4. Can you do as well or better?
"I can come back two days from now for an average no greater than 6 or 7."
Reader: Liane was able to get 121 with an average cost of just under 6. She was able to get 308 with an average cost of just under 7. She didn't always use the same generator. How well do you do?
Ecco turned to me after our visitor left.
"Well Professor, you see the numbers Liane has come up with: 57 for an average cost of 5, 121 for an average cost of 6, and 308 for an average cost of 7. Is there an exponential relationship with the average cost? Further, what does the average cost vary with the number of generators you are permitted to use (for example, if you used 4 and 5 together as generators instead of just 5)?
"I don't know the answers."
Reader: What do you think?
Last Month's Solution
Figure 1, Liane's solution to last month's puzzle, using six rays.
Reader Notes
The following readers proposed correct solutions to the "With Eye of Newt" puzzle (DDJ, March 2002): Pearl Pauling, Craig Stevenson, Warren Dougherty, Andrew Palfreyman, Douglas Michael Auclair, Rodney Meyer, Douglas Wilson, Mike Bandy, and Mani Iyer.
The glue-machine technology as proposed in this puzzle would be extremely useful. Physicists and chemists, please take note.
DDJ
