Are there any multiple digit hexadecimal number palindromes that are also palindromic in binary and decimal? I have been searching but have not found any.
I started my search with my program that finds multiple-base palindromes. I generated palindromes in binary, and then checked them to see if they were also palindromes in hexadecimal and decimal. I looked for decimal/binary/hexadecimal palindromes up to 16 hex digits long, but did not find any.
To continue my search into bigger numbers, I wrote a program that uses arbitrary-precision integer arithmetic and a more efficient algorithm. Despite being able to search much further, I still have not found any.
In this article, I’ll analyze the size of the palindrome “search space”, explain my improved algorithm, and discuss the state of my search.
Search Space for Decimal/Binary/Hexadecimal Palindromes
The biggest obstacle in the search for palindromes is the growth in the amount of numbers that must be checked — the search space. As the number of digits increases, the search space grows exponentially. While this exponential growth can’t be eliminated, it can be delayed — by pruning the search space.
Consider the search space for 32 hexadecimal digit decimal/binary/hexadecimal palindromes. With no pruning, 15·1631 integers would have to be checked — 319,014,718,988,379,809,496,913,694,467,282,698,240 numbers, an impossible task. If only hexadecimal palindromes are considered, the search space is reduced to 15·1615 = 17,293,822,569,102,704,640 numbers — much smaller but still intractable. If only binary/hexadecimal palindromes are considered, then there are 216 + 232 = 4,295,032,832 numbers to be checked — quite manageable!
The binary/hexadecimal palindrome space can be partitioned by starting digit so that subsets can be searched independently. Consider the 32 hexadecimal digit binary/hexadecimal palindromes. There are 216 = 65,536 that begin with the digits 1 and 3, and 232 = 4,294,967,296 that begin with the digits 5, 7, 9, and F. The number of palindromes that start with 1 and 3 is markedly lower, allowing for a deeper search within them.
The following diagrams illustrate how the search space grows, showing the search spaces for the 16, 32, and 64 digit hexadecimal palindromes:
Program to Find Decimal/Binary/Hexadecimal Palindromes
I wrote a C program to search for decimal/binary/hexadecimal palindromes — it is based on two things:
- Arbitrary-precision integers.
This allows for palindrome numbers that are too big to fit in an unsigned long long integer variable; that is, numbers bigger than 64 bits, or 16 hex digits. I used GMP in Visual C++ on Windows.
- Direct generation of binary/hexadecimal palindromes.
This reduces the search space dramatically, so that only known binary/hexadecimal palindromes are checked — for being palindromic in decimal. I used a simple algorithm derived from my analysis of binary/hexadecimal palindromes.
I will outline the algorithm instead of providing the source code.
The Algorithm
Binary/hexadecimal palindromes could be generated in two ways. One way would be incrementally, by generating the two-digit palindromes, then the three-digit palindromes, then the four-digit palindromes, etc. A set of m-digit palindromes would be built from a set of m-1 digit palindromes, by inserting a digit in the middle of each m-1 digit palindrome. This requires storage of palindromes, which will not scale — the number of palindromes grows exponentially.
Another way to generate binary/hexadecimal palindromes — the way I chose — is to construct them from permutations of hex digits. Each of the six subsets of binary/hexadecimal palindromes has its own rules for valid digits:
- Starts/ends with 1: each digit between can be 0 or 1
- Starts/ends with 3: each digit between can be 0 or 3
- Starts/ends with 5: each digit between can be 0, 2, 5, or 7
- Starts/ends with 7: each digit between can be 0, 2, 5, or 7
- Starts/ends with 9: each digit between can be 0, 6, 9, or F
- Starts/ends with F: each digit between can be 0, 6, 9, or F
You construct palindromes of n digits from permutations of floor(n/2) digits. For example, to generate a 32 digit palindrome that starts with 5, create a number that starts with 5 followed by a 15 digit permutation of the digits 0, 2, 5, and 7. Then, reverse that number and append it to itself to create a 32 digit palindrome. (The process for odd length palindromes is similar, except you insert an extra middle digit between the two halves.)
Permutations are easily generated, with a series of nested loops. You can nest loops statically, by coding a loop for each place of the permutation, or you can nest them dynamically, by calling a single loop recursively. The advantage of dynamic nesting is not having to add loops manually for increasing digit lengths; the advantage of static nesting is the ability to “checkpoint” the state of the search easily — an important feature for long running programs. I chose static nesting for that reason.
Results
I’ve searched the “1/3 space” through all 64 hex digit numbers, and the “5/7/9/F space” through all 32 hex digit numbers. I have not found a single multi-digit decimal/binary/hexadecimal palindrome.
I have suspended my search, since the running time of my program is starting to explode. For example, it took almost 60 hours on my Intel Core Duo processor to test all 232 64 hex digit binary/hexadecimal palindromes in the 1/3 space. Resuming the search would probably require a GIMPS-like distributive computing approach, which I have no plans to undertake.
Discussion
Are there any tricks to reduce the search space further, delaying the inevitable exponential explosion even more? Charlton’s binary/decimal palindrome search algorithm eliminates swaths of numbers as it runs, recognizing conditions under which copalindromic numbers can’t exist. Can similar ideas be applied to the search for decimal/binary/hexadecimal palindromes?
Another Way to Count Binary/Hexadecimal Palindromes
In my article “Counting Binary/Hexadecimal Palindromes” I derived formulas to count binary/hexadecimal palindromes using geometric series. An alternate way would be based on counting permutations. For example, the number of 32 digit palindromes starting with 5 is the number of 15 digit permutations of the digits 0, 2, 5, and 7; that is, 415 = 230 = 1,073,741,824.
(You would still need geometric series to count the number of palindromes of n-digits or less.)
Are There Any?
Are there any decimal/binary/hexadecimal palindromes? Can it be proved either way?
I have no reason to believe they don’t exist. After all, there are at least two multi-digit decimal/binary/octal palindromes. And it’s always possible I made an error in my search, although Charlton’s results confirm my results through 32 hex digits plus.
