# The Structure of Binary/Hexadecimal Palindromes

Binary/hexadecimal palindromes are integers that are palindromic in both binary and hexadecimal. Unlike binary/decimal palindromes, for example, they have a predictable structure. This means they can be generated directly, rather than searched for. So what is their structure?

Certainly they’re made up of the hexadecimal digits that are themselves palindromic in binary: 0, 6, 9, F; for example, F060F16 = 111100000110000011112 and 9F916 = 1001111110012. Each of these four hexadecimal digits maps neatly to a 4-digit binary palindrome, so any hexadecimal palindrome made from them is automatically palindromic in binary.

But there are other binary/hexadecimal palindromes, like 52516 = 101001001012 and 7020716 = 11100000010000001112, that contain hexadecimal digits that are not palindromic in binary. In this case, binary palindromes are produced with combinations of hexadecimal digits. It turns out there are a limited number of valid combinations, and that they’re localized — they span only two hexadecimal digits.

In this article, I’ll analyze binary/hexadecimal palindromes and describe their structure — a structure due to the relationship of the two bases, binary and hexadecimal.

## Inferring the Structure of Binary/Hexadecimal Palindromes

Before determining the structure of binary/hexadecimal palindromes analytically, let’s look at more examples. I listed the first 124 (nonzero) binary/hexadecimal palindromes — that is, those palindromes consisting of five hexadecimal digits or less — using my C program that finds multi-base palindromes. I noticed that each palindrome starts (and thus ends) with one of six hexadecimal digits: 1, 3, 5, 7, 9, F. I also noticed that, depending on the starting digit, only certain middle digits appear:

• Palindromes starting with 1: only 0 and 1 appear as middle digits.
• Palindromes starting with 3: only 0 and 3 appear as middle digits.
• Palindromes starting with 5 or 7: only 0, 2, 5, and 7 appear as middle digits.
• Palindromes starting with 9 or F: only 0, 6, 9, and F appear as middle digits.

Within each of the four groups of palindromes, the middle digits alternate in each digit position, in the order listed above.

Here is the output of my program, segmented by starting digit (the highlighted digits in the hexadecimal palindromes are the digits “inserted” into them to take them from n digits to n+1 digits):

Palindromes starting with hex ‘1’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with 116)
116 12
1116 100012
10116 1000000012
11116 1000100012
100116 10000000000012
111116 10001000100012
1000116 100000000000000012
1010116 100000001000000012
1101116 100010000000100012
1111116 100010001000100012

Palindromes starting with ‘3’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with 316)
316 112
3316 1100112
30316 11000000112
33316 11001100112
300316 110000000000112
333316 110011001100112
3000316 1100000000000000112
3030316 1100000011000000112
3303316 1100110000001100112
3333316 1100110011001100112

Palindromes starting with hex ‘5’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with 516)
516 1012
5516 10101012
50516 101000001012
52516 101001001012
55516 101010101012
57516 101011101012
500516 1010000000001012
522516 1010010001001012
555516 1010101010101012
577516 1010111011101012
5000516 10100000000000001012
5020516 10100000010000001012
5050516 10100000101000001012
5070516 10100000111000001012
5202516 10100100000001001012
5222516 10100100010001001012
5252516 10100100101001001012
5272516 10100100111001001012
5505516 10101010000010101012
5525516 10101010010010101012
5555516 10101010101010101012
5575516 10101010111010101012
5707516 10101110000011101012
5727516 10101110010011101012
5757516 10101110101011101012
5777516 10101110111011101012

Palindromes starting with hex ‘7’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with 716)
716 1112
7716 11101112
70716 111000001112
72716 111001001112
75716 111010101112
77716 111011101112
700716 1110000000001112
722716 1110010001001112
755716 1110101010101112
777716 1110111011101112
7000716 11100000000000001112
7020716 11100000010000001112
7050716 11100000101000001112
7070716 11100000111000001112
7202716 11100100000001001112
7222716 11100100010001001112
7252716 11100100101001001112
7272716 11100100111001001112
7505716 11101010000010101112
7525716 11101010010010101112
7555716 11101010101010101112
7575716 11101010111010101112
7707716 11101110000011101112
7727716 11101110010011101112
7757716 11101110101011101112
7777716 11101110111011101112

Palindromes starting with hex ‘9’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with 916)
916 10012
9916 100110012
90916 1001000010012
96916 1001011010012
99916 1001100110012
9F916 1001111110012
900916 10010000000010012
966916 10010110011010012
999916 10011001100110012
9FF916 10011111111110012
9000916 100100000000000010012
9060916 100100000110000010012
9090916 100100001001000010012
90F0916 100100001111000010012
9606916 100101100000011010012
9666916 100101100110011010012
9696916 100101101001011010012
96F6916 100101101111011010012
9909916 100110010000100110012
9969916 100110010110100110012
9999916 100110011001100110012
99F9916 100110011111100110012
9F0F916 100111110000111110012
9F6F916 100111110110111110012
9F9F916 100111111001111110012
9FFF916 100111111111111110012

Palindromes starting with hex ‘F’:

Binary/Hexadecimal Palindromes (1-5 Hex Digits, Starting with F16)
F16 11112
FF16 111111112
F0F16 1111000011112
F6F16 1111011011112
F9F16 1111100111112
FFF16 1111111111112
F00F16 11110000000011112
F66F16 11110110011011112
F99F16 11111001100111112
FFFF16 11111111111111112
F000F16 111100000000000011112
F060F16 111100000110000011112
F090F16 111100001001000011112
F0F0F16 111100001111000011112
F606F16 111101100000011011112
F666F16 111101100110011011112
F696F16 111101101001011011112
F6F6F16 111101101111011011112
F909F16 111110010000100111112
F969F16 111110010110100111112
F999F16 111110011001100111112
F9F9F16 111110011111100111112
FF0FF16 111111110000111111112
FF6FF16 111111110110111111112
FF9FF16 111111111001111111112
FFFFF16 111111111111111111112

You can see that binary palindromes starting with hex digits 1, 3, 5, and 7 are not multiples of four bits. This is because leading zeros do not count. Each of those four hex digits — when used as a starting digit — requires less than four bits. In this case, it’s important to remember that hex digits are formed in groups of four bits, from right to left.

## Starting Digits

We’ve seen empirically that a nonzero binary/hexadecimal palindrome starts with the hexadecimal digit 1, 3, 5, 7, 9, or F — now it’s time to prove it.

First, observe that the starting hex digit must be odd: an even hex digit ends with a 0 when written in binary, and palindromes can’t start with 0. This leaves eight starting digits as candidates: 1, 3, 5, 7, 9, B, D, F.

Let’s classify our palindromes into two categories: single hex digit and multiple hex digit. A single hex digit palindrome is a single hex digit that is palindromic in binary: 1, 3, 5, 7, 9, and F are the only choices (116 = 12, 316 = 112, 516 = 1012, 716 = 1112, 916 = 10012, F16 = 11112). A multiple hex digit palindrome as a whole is palindromic in binary, but individually, each hex digit may not be — and in fact, will not be — palindromic in binary.

Let’s analyze multiple hex digit palindromes by classifying them into two categories, depending on whether their ending hex digit has a binary equivalent that starts with a 1 or 0:

• Binary equivalent starts with 1.

The hexadecimal palindrome will have an associated binary palindrome that is a multiple of four bits. This means that each hex digit must stand alone as a binary palindrome: 9 and F are the only choices for the starting digit. There are two 2-digit palindromes that start with 9 and F: 9916 = 100110012 and FF16 = 111111112; these will serve as “bookends” for all palindromes of 3 digits or more.

• Binary equivalent starts with 0.

The hexadecimal palindrome will have an associated binary palindrome that is not a multiple of four bits. This means that each hex digit does not stand alone as a binary palindrome.

The best way to show which starting digits are allowed in this case is to try all four candidates as 2-digit palindromes: 1116 = 100012, 3316 = 1100112, 5516 = 10101012, and 7716 = 11101112. All are binary palindromes, so 1, 3, 5, 7 are the valid starting digits.

## Middle Digits

We’ve seen empirically what the middle digits of multiple digit binary/hexadecimal palindromes are, and that they follow a pattern — now I’ll show why.

Definition. I’ll say a number is a leading-zero palindrome or is leading-zero palindromic if it is palindromic with zero or more leading zeros.

### Middle Digits for Starting Digits 9, F

Palindromes starting with 9 or F are straightforward to analyze, so I’ll start with them. Each middle hex digit must stand alone as a leading-zero binary palindrome, so 0, 6, 9, and F are the choices.

The structure of these palindromes is easy to describe. The n+1 hex digit palindromes can be created from the n hex digit palindromes by inserting the digits 0, 6, 9, or F. When n is odd, one n+1 digit palindrome is spawned from each n digit palindrome, by replicating the middle hex digit (which will be 0, 6, 9 or F). When n is even, four n+1 digit palindromes are spawned from each n digit palindrome, by inserting the digits 0, 6, 9, and F in turn.

### Middle Digits for Starting Digits 1, 3, 5, 7

The analysis of palindromes starting with 1, 3, 5, or 7 is based on the number of leading zeros in the binary representation of the ending hex digit; let’s define the three cases:

• 1 leading zero: 5 (0101) and 7 (0111).
• 2 leading zeros: 3 (0011).
• 3 leading zeros: 1 (0001).

Recall how palindrome generation works: each inserted hex digit takes an n digit palindrome and turns it into an n+1 digit palindrome. To ensure the result remains a binary palindrome, the inserted hex digit must maintain a binary palindrome around the “center”. Here’s how it’s done:

• The binary representation of the inserted hex digit must have the same number of leading zeros as the binary representation of the hex digit to its right.
• The binary representation of the inserted hex digit must be palindromic without the leading zeros.

In other words, the inserted leading zeros mirror the existing leading zeros, and the rest of the hex digit — which is between the sets of zeros — stands alone as a binary palindrome.

(There’s an alternate way to think of this: the inserted hex digit, with the one, two, or three leading binary zeros in the hex digit to its right, is a leading zero palindrome. The left side of this palindrome replaces the leading zeros used from the right.)

So what are the allowable middle digits? Hex digits 0-7 are the candidates, since they’re the only 4-bit hex digits that have leading zeros in their binary representations. But after you strip away the required number of leading zeros, only 0, 1, 2, 3, 5, and 7 stand alone as binary palindromes:

• 1 leading zero: 0 (000), 2 (010), 5 (101), 7 (111).
• 2 leading zeros: 0 (00) or 3 (11).
• 3 leading zeros: 0 (0) or 1 (1).

The insertion of middle digits can continue indefinitely, since the number of binary leading zeros in each group is the same for each digit. Any middle digit in each group can be adjacent to any other. The number of leading zeros in the ending digit is the number of leading zeros maintained throughout.

#### Example

This diagram shows an example of binary/hexadecimal palindrome generation:

## Summary

In summary, the (nonzero) binary/hexadecimal palindromes are

• The single digit hexadecimal palindromes 1, 3, 5, 7, 9, and F.
• All hexadecimal palindromes that start and end with 1 and have only 0s and 1s between.
• All hexadecimal palindromes that start and end with 3 and have only 0s and 3s between.
• All hexadecimal palindromes that start and end with 5 or 7 and have only 0s, 2s, 5s, and 7s between.
• All hexadecimal palindromes that start and end with 9 or F and have only 0s, 6s, 9s, and Fs between.

(And now that we know their structure we can count them — see my article “Counting Binary/Hexadecimal Palindromes”.) 