Three Years Of Computing

Final Report On The Palindrome Quest

by John Walker
May 25th, 1990

Pick a number. Reverse its digits and add the resulting number to the original number. If the result isn't a palindrome, repeat the process. Do all numbers in base 10 eventually become palindromes through this process? Nobody knows.[1]

For example, start with 87. Applying this process, we obtain:

    87 + 78 = 165
              165 + 561 = 726
                          726 + 627 = 1353
                                      1353 + 3531 = 4884, a palindrome

In order for addition of a digits-reversed number to yield a palindrome, there must be no carries in the addition and hence each pair of digits must sum to 9 or less.

Whether all numbers eventually become palindromic under this process is unproved, but all numbers less than 10,000 have been tested. Every one becomes a palindrome in a relatively small number of steps (of the 900 3-digit numbers, 90 are palindromes to start with and 735 of the remainder take less than 5 reversals and additions to yield a palindrome). Except, that is, for 196. This number had been carried through 50,000 reversals and additions by P. C. Leyland, yielding a number of more than 26,000 digits without producing a palindrome. Later, P. Anderton continued the process up to 70,928 digits without encountering a palindrome.

On August 12, 1987, I put my Sun 3/260 to work on this problem. A program, pquest.c, performs the reversal and addition of arbitrary precision numbers and checks for a palindrome after each step. The program runs with a nice(15) priority, mopping up all available compute cycles while instantly relinquishing the CPU to normal foreground jobs. (There is no perceptible degradation in system performance when this program is running. You do have to get used to seeing your CPU meter pegged at 100% all the time, however.)

The program writes checkpoints to a file every two hours and works in conjunction with a set of shell scripts that restart it from the most recent checkpoint and shut it down with a current checkpoint when the system is being shut down. This allows the process to continue day in and day out without human intervention.

For almost three years the process of reversal and addition continued. Last night, at five minutes before midnight, the program printed the message:

        Stop point reached on pass 2415836.
        Number contains 1000000 digits.

and exited. The built-in endpoint had been reached; after 2,415,836 reversals and additions, 196 had grown to a number of 1,000,000 digits without ever yielding a palindrome. Does it ever produce one? Still, nobody knows. From a probabilistic standpoint, as a number grows to enormous size the likelihood of producing a palindrome on the next step decreases since the odds of a digit pair summing to 10 or more approach certainty in very large numbers. But with infinite repetition of this process…perhaps.

I will leave it at a million digits after three years of computing. The program that conducted the Quest is available for you to download. If you'd like to continue the Great Work yourself, you can download the million-digit result of the original computation so you don't have to repeat it.

What use is this? Well, none, really, but how useful is the idle loop on your computer?

I'm not planning to publish this result because after 3 years of enduring the vicissitudes of a Motorola 68020 microprocessor, I wouldn't be confident in the results without re-running them for verification and I'm not about to re-up for another 3 years. Besides, if I wait 2 years, I'll probably have a computer on my desk that can do it in 6 months—it's just like the phenomenon of slowboat interstellar travel: no matter when you leave, by the time you get there the destination is already populated by the descendants of people who left after you and traveled in faster ships built with later technology.

All of this raises a question I've been meaning to pose for some time now. Are there useful and/or interesting tasks which can be done in the background on our workstations? In particular, are there tasks which can exploit the latent supercomputer power of the idle cycles on all the Sun workstations on the Ethernet at the office in a collaborative fashion?

While these kinds of tasks have traditionally been recreational math record-busting like the 196 Palindrome Quest, I'm particularly interested in potential candidate problems more closely related to the real world such as numerical simulations of the evolution of gravitationally bound systems like globular clusters and models of galaxy formation, numerical solutions of difficult problems in quantum mechanics, and the like. I'd rather go after something like that than mount another hackneyed assault on the largest Mersenne prime.

Obviously, all such endeavours are low priority in the human domain as well as the operating system process dispatch queue.

1995 Addendum: The Crunch Goes On

In 1995, Tim Irvin, finding himself in the vicinity of a supercomputer with time on its hands, decided to carry on the Quest, starting with the million digit number I stopped at in 1990. It's indicative of progress in computing that it took just two months to carry the Quest to the two million digit mark—without finding a palindrome. Read the story of his continuation of the Quest for details. The two million digits he computed are available for you to download.