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, F060F₁₆ = 11110000011000001111₂ and 9F9₁₆ = 100111111001₂. 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 525₁₆ = 10100100101₂ and 70207₁₆ = 1110000001000000111₂, 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’:

Palindromes starting with ‘3’:

Palindromes starting with hex ‘5’:

Palindromes starting with hex ‘7’:

Palindromes starting with hex ‘9’:

Palindromes starting with hex ‘F’:

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 (1₁₆ = 1₂, 3₁₆ = 11₂, 5₁₆ = 101₂, 7₁₆ = 111₂, 9₁₆ = 1001₂, F₁₆ = 1111₂). 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: 99₁₆ = 10011001₂ and FF₁₆ = 11111111₂; 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: 11₁₆ = 10001₂, 33₁₆ = 110011₂, 55₁₆ = 1010101₂, and 77₁₆ = 1110111₂. 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”.)