Ivars Peterson's MathTrek

May 10, 1999

# Palindromic Primes

In the zoo of prime numbers, there are certain species that attract an inordinate amount of attention. Among these curiosities are the so-called palindromic primes--whole numbers, evenly divisible only by themselves and 1, that also have the same sequence of digits read forward or backward.

In the realm of palindromic primes, 11 is the only one with an even number of digits. Every other palindrome having an even number of digits is divisible by 11 and so can't be prime. For example, 98,766,789 equals 11 times 8,978,799.

There are 15 palindromic primes consisting of three digits: 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, and 929.

The smallest prime of length 7 containing only the digits 7 and 8 is palindromic: 7778777. The smallest palindromic prime containing all 10 digits is 1023456987896543201. The list of numerical curiosities discovered by amateur mathematicians and numerologists playing with palindromes goes on and on.

The current record for the largest known palindromic prime is held by Harvey Dubner, a retired electrical engineer in New Jersey. Flushed out of hiding late last month, the record holder consists of 30,803 digits, each of them either 1 or 0. It's the sort of prime that reads the same forward, backward, upside down, and rotated.

It's also the largest known prime that is not of the form a x bn 1, Dubner notes.

Notice that 30803 is itself a palindromic prime. That's not an accident, Dubner says. It's a consequence of the method he uses for capturing palindromic primes.

Dubner starts with a number of the form 10000. . .00001 with a palindromic-prime number of digits. For example, the number of digits could be 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, or 32423. He then inserts a small palindrome into the middle of his starting number to give, say, 10000. . .00012321000. . .00001. That number is tested for primality, first by trial division to uncover any small factors, then by using more sophisticated techniques. If the number isn't prime, he changes the central number to a different palindrome, repeating the process. Dubner can have as many as seven computers in operation, each one looking at a different number of palindromic-prime digits.

What's the secret of Dubner's success? "Many, fast computers; efficient, fast software; and luck," he says.

Dubner had estimated that it would take him the equivalent of about 233 days on a 200-MHz Pentium computer to find the latest record holder, 1000. . .0001110111000. . .0001. Instead, it took only 12 days. "With this kind of luck, maybe I should start playing the lottery," he says.

The previous record, set by Dubner last February, was the 19,391-digit prime 1000. . .0004300034000. . .0001.