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.

Example Binary/Hexadecimal Palindromes
Example Binary/Hexadecimal Palindromes

Continue reading “The Structure of Binary/Hexadecimal Palindromes”

Counting Binary and Hexadecimal Palindromes

How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:

  • When n is even: 9·10n/2-1
  • When n is odd: 9·10(n+1)/2-1

How many nonzero, decimal number palindromes are there, consisting of n-digits or less? These two formulas give the answer:

  • When n is even: 2(10n/2 – 1)
  • When n is odd: 11·10(n-1)/2 – 2

So for example, there are 900 5-digit decimal palindromes, 9,000 8-digit decimal palindromes, 1,098 decimal palindromes of 5 digits or less, and 19,998 decimal palindromes of 8 digits or less.

In this article, I will derive similar formulas to count binary and hexadecimal number palindromes.

Continue reading “Counting Binary and Hexadecimal Palindromes”