A man, a plan, a canal, Panama.
Bombard a drab mob.
Drab as a fool, aloof as a bard.
Palindromes are strings that can be read the same backwards as forwards. The most common palindromes are words or sentences, but palindromes can be made from any set of characters. Lately I’ve been interested in palindromic numbers, which are numbers (like 1221 and 5567655) where the the nth digit from the beginning is the same as the nth digit from the end.
Palindromic numbers are pretty easy to generate. Just choose a length for the number, then choose some digits for the first half of the number. Mirror those, and you’ve got a number. They’re easier to make than palindromic sentences, because numbers don’t have to make any kind of logical sense. They’re kind of like my symmetric egg basket problem, where choosing one half of a solution defines the other half.
In text, palindromes are kind of rare. Palindromes that actually make sense are rarer still. I wanted to see how rare palindromes are in the natural numbers. It turns out that the density of palindromic numbers decreases exponentially as the magnitude of the number increases.
Every single one digit number is a palindrome. There are nine two digit palindromes (the multiples of 11). Three digit palindromes start to get a little more interesting. Any combination of two digits leads to a palindrome of three digits by copying the first digit as the third. This puts the number of three digit palindromes at 9*10 = 90. There are nine choices for the first digit (we exclude zero) and ten choices for the second digit. Four digit palindromes can be counted in the same way, since instead of copying the first digit you copy both first two.
Continuing on in this way, we can find the percentage of numbers of each order of magnitude that are palindromes:
1 digit: 100%
2 digits: 10% (9 palindromes in 90 numbers)
3 digits: 10% (90 palindromes in 900 numbers)
4 digits: 1% (90 palindromes in 9000 numbers)
5 digits: 1% (9*10*10=900 palindromes in 90000 numbers)
6 digits: .1% (900 palindromes in 900000 numbers)
7 digits: .1% (9*10*10*10=9000 palindromes in 9 million numbers)
Every two orders of magnitude that we go up decreases the percentage of palindromes by an order of magnitude. The number of palindromes only increases with two jumps in the size of the number, but the total number of numbers increases with each jump in the size of the number. This is why the percentage of palindromes will slowly decrease.
Just for fun, I also decided to compare palindromes in one base to palindromes in another. I wrote a python script that would compare decimal palindromes to their hex equivalent and report any hex values it found that were also palindromes.
#check decimal palindromes for hex palindromes
def convHex(decimal_string):
hex_string = str(hex(int(decimal_string)))[2:]
is_palindrome = True
for i in range(len(hex_string)):
if hex_string[i] != hex_string[-(1+i)]:
is_palindrome = False
#end if
#end for
if is_palindrome:
return [int(decimal_string)]
else:
return []
#end if
#end def convHex(decimal_string)
double_palindromes = []
for i in range(1,10000):
#even number of digits
palindrome = str(i) + str(i)[::-1]
double_palindromes.extend(convHex(palindrome))
#odd number of digits
palindrome = str(i) + str(i)[-2::-1]
double_palindromes.extend(convHex(palindrome))
#end for
double_palindromes.sort()
for i in double_palindromes:
print i, hex(i)
Again, all one digit numbers are palindromes for every base. Since hex has all the single digits that decimal does, all single digit decimal palindromes are palindromes in hex as well. After that, the numbers that are palindromes in both bases get far rarer.
Here’s the list of all numbers up under 9 digits long that are palindromes in both decimal and hex bases:
1 0x1
2 0x2
3 0x3
4 0x4
5 0x5
6 0x6
7 0x7
8 0x8
9 0x9
11 0xb
353 0x161
626 0x272
787 0x313
979 0x3d3
1991 0x7c7
3003 0xbbb
39593 0x9aa9
41514 0xa22a
90209 0x16061
94049 0x16f61
96369 0x17871
98689 0x18181
333333 0x51615
512215 0x7d0d7
666666 0xa2c2a
749947 0xb717b
845548 0xce6ec
1612161 0x189981
2485842 0x25ee52
5614165 0x55aa55
6487846 0x62ff26
9616169 0x92bb29
67433476 0x404f404
90999909 0x56c8c65
94355349 0x59fbf95
94544549 0x5a2a2a5
Wikipedia has a lot more information on palindromic numbers. Apparently they’re pretty common in mathematical riddles and puzzle challenges.