Dr. Dobb's Journal January, 2005
Ecco encouraged his niece and nephew to bring over their friends whenever they wanted. Most people would have considered Camille and Maia to be very unusual teenagers. Naturally, they fit right into the Ecco household. Good-looking girls with a fine sense of music, they accompanied Liane's singing and guitar strumming using Tyler's drums.
"Our England-born Dad heard this game from a school teacher back in the day," Camille told us after the singing had stopped.
"Now it's going to give us a hint about a secret phone number. The game is called 'four 4s.' The idea is that you want to set up an arithmetic expression to give you as many consecutive integers as possible using the digit 4 alone, at most four times. For example, you can get 1 by dividing 4 by itself and 2 by taking the square root of 4.
"The expression may include the following operators: addition, subtraction, multiplication, division, square root, exponentiation (for example, 44), concatenation (44, which uses 4 twice), decimal 0.4, decimal repeat 0.4R=0.4444444444...= 4/9 (this uses 4 once), factorial (4!=24, for example), and parentheses (to distinguish (4+4)/4 from 4+(4/4))."
Warm-Up: It is possible to find expressions for the numbers 1 through 10 under these constraints. If you try really hard, you can use three 4s or fewer for every number. Try it before you read on.
Solution to Warm-Up:
1=4/4
2=sqrt(4)
3 =sqrt(4/.4R) = sqrt(4/(4/9)) = sqrt(9)
4=4
5=sqrt(4)/0.4
6=4 + sqrt(4)
7=4/.4R - sqrt(4)
8=4*sqrt(4)
9=4/.4R
10=4/.4
"We have had trouble going much beyond this. We believe that the first numbers that can't be expressed in terms of four or fewer 4s (we call those "gaps") give us a good hint as to the 10-digit U.S. secret phone number. Are there any gaps below 40?"
"I don't think so," said Tyler proceeding to show encodings for those numbers.
"Nice use of factorial," Maia said smiling.
Tyler found expressions for 11 to 40 using at most four 4s per integer. All but one of the numbers below 30 could be constructed using three 4s or fewer. Can you do as well or better?
The girls left, quite satisfied with their meeting, but Liane was quite annoyed.
"Tyler, we should have been able to help them more. Here are some open problems:
"Open 1. How far can we go under these rules?
"Open 2. How many of the integers between 1 to 1000 can be handled with just four 4s? What are the first gap numbers? Do any of those gaps make sense as phone numbers?
"Open 3. If we were allowed five 4s, what is the longest sequence of consecutive integers we could produce? (It doesn't have to start at 1.)"
Tyler smiled and said, "I've worked on the four 4s question up to 100. Beyond that I don't know."
I had to leave before seeing his answer. It's now open season on the open questions.
DDJ