The Reversible Phone Number

Consider this problem: An absent-minded American mathematician has difficulty remembering his seven-digit phone number until he notices that, when he reverses the digits, he gets another seven-digit phone number that is a factor of his own phone number. After this point, he never has trouble with his number again. What is his phone number? (This is an adaptation of a problem from Aaron J. Friedland, Puzzles in Math and Logic [Dover Press].)

 Solution

This is a job for brute force. We can make certain assumptions about the characteristics of the number (it’s probably a multiple of 2 or 3, for instance), but since we have computers readily available, I like to get some data first and then look for patterns.

Let’s look at the limitations. We rule out the trivial palindromic numbers (555-0555) as well as numbers whose reversals have leading zeroes (383-0000 and 980-1000). We’re to look for seven-digit numbers that have different seven-digit reversals which are factors. There are in fact only two of these: 8799912 and 9899901: [frac{8,799,912}{4} = 2,199,978\ frac{9,899,901}{9} = 1,099,989]

Only one of these factors can be a U.S. phone number, since three-digit exchanges can’t start with 1 (I understand this is a carry-over from the analog days, when a 1 at the beginning of a phone number triggered a long-distance call). Hence, the professor’s phone number is 879-9912.

Notice both of the numbers have three 9s in the middle. That’s actually relevant. This is where it gets cool.

What about other lengths?

So, what about other lengths? In order to crunch through this problem, I had written a quick Excel VBA subroutine. Inelegant and slow, but hey, it did its job. I gave it some minor tweaks to find all the non-palindromic numbers with a length from two to nine digits that have a reversal of the same number of digits. I stopped at nine for pragmatic reasons: Excel VBA’s long data type can’t handle all ten-digit numbers (its max is 2,147,483,647). As it turns out, though, Excel took about ten minutes on the nine digit numbers anyway, so it’s just as well I couldn’t keep going. Besides, a pattern had emerged at that point.

Here’s my subroutine, for the curious:

Sub FlipItGood()
    Dim StringLength As Integer, FactorToCheck As Long, ValueToCheck As Long, FactorTest As Double
    Dim ValueHoppers() As Integer, NumberPlace As Integer
    For StringLength = 2 To 9
        ReDim ValueHoppers(StringLength) As Integer
        For FactorToCheck = 10 ^ (StringLength - 1) To 5 * 10 ^ (StringLength - 1)
            For NumberPlace = 1 To StringLength
                ValueHoppers(NumberPlace) = Int(FactorToCheck / 10 ^ (NumberPlace - 1)) Mod 10
            Next NumberPlace
            ValueToCheck = 0
            For NumberPlace = 1 To StringLength
                ValueToCheck = ValueToCheck + ValueHoppers(StringLength - NumberPlace + 1) * 10 ^ (NumberPlace - 1)
            Next NumberPlace
            FactorTest = ValueToCheck / FactorToCheck
            If FactorTest = Int(FactorTest) And FactorTest > 1 Then
                Debug.Print FactorToCheck, ValueToCheck, FactorTest
            End If
        Next FactorToCheck
    Next StringLength
End Sub

And here is its output:

 1089          9801          9
 2178          8712          4
 10989         98901         9
 21978         87912         4
 109989        989901        9
 219978        879912        4
 1099989       9899901       9
 2199978       8799912       4
 10891089      98019801      9
 10999989      98999901      9
 21782178      87128712      4
 21999978      87999912      4
 108901089     980109801     9
 109999989     989999901     9
 217802178     871208712     4
 219999978     879999912     4

The first thing I noticed is that there are no two or three digit numbers that satisfy the constraints: The output starts at 4.

The second thing I noticed is that, for four to seven digits, there are two solutions, one a multiple of 4 and the other a multiple of 9. Notice that 4 and 9 are square numbers, the only one-digit squares.

The most intriguing thing that I noticed is that there’s a repeated pattern. Every solution has 87*12 or 98*01. Insert any number of 9s in place of the asterisk and you’ll get a number that satisfies the constraints. Starting with eight digits, we get two new values: 8712~8712 and 9801~9801. In this pattern, replace the tilde with any number of 0s.

At ten digits, by the way, we get two more new values: 8791287912 and 9890198901. We can generalize this with the eight-digit numbers to 87*12~87*12 and 98*01~98*01. Starting with twelve digits, we get some more new values: 871287128712, 879912879912, 980198019801, and 989901989901. I haven’t done the analysis to prove that this is an exhaustive list, but these numbers do satisfy the constraints.

Generalizing: Let’s Go All the Way

In fact, I’m willing to generalize that any number which follows the established pattern satisfies the constraints:

1. Start with 8712 or 9801.
2. Insert some arbitrary number of 9s in the middle.
3. Duplicate at will.
4. Insert some arbitrary number of 0s between the clones (making sure it’s the same number between each clone).

So let’s try it:

1. 8712
2. 8799912
3. 8799912879991287999128799912
4. 8799912000879991200087999120008799912

WolframAlpha confirms that our algorithm works.