Counting Binary/Hexadecimal Palindromes

In my article “Counting Binary and Hexadecimal Palindromes” I derived formulas for counting binary palindromes and hexadecimal palindromes. For each type of palindrome, I derived two pairs of formulas: one pair to count n-digit palindromes, and one pair to count palindromes of n digits or less.

In this article, I will derive similar formulas to count binary/hexadecimal palindromes — multi-base palindromes I’ve shown to have an algorithmically defined structure.

Binary/Hexadecimal Palindromes of n Hexadecimal Digits

To derive the formula to count binary/hexadecimal palindromes, look at the tables in my article “The Structure of Binary/Hexadecimal Palindromes”. There’s a table of palindromes for each starting hexadecimal digit: 1, 3, 5, 7, 9, and F. Each table lists the binary/hexadecimal palindromes of one to five hex digits, for each starting digit. If you count the palindromes in the tables — and continue the pattern beyond five digits — this is what you’ll get:

This pattern continues forever, based on the structure of the palindromes.

(Notice we’re not counting 0 as a palindrome — if you want to, add 1 to the formulas we derive below.)

There are two different count sequences: one of interleaved nonnegative powers of two, and one of interleaved nonnegative powers of four. As we learned when counting n-digit binary palindromes, the sequence of interleaved nonnegative powers of two is captured by these two formulas:

• When n is even: 2^n/2-1
• When n is odd: 2^(n+1)/2-1

Those two formulas apply to the starting hex digits 1 and 3, counting the number of n hex digit binary/hexadecimal palindromes for each.

You can use similar formulas to generate the sequence of interleaved nonnegative powers of four:

• When n is even: 4^n/2-1 = 2^2·(n/2-1) = 2^n-2
• When n is odd: 4^(n+1)/2-1 = 2^{2·((n+1)/2-1)} = 2^n-1

(It should not be surprising that these expressions simplify to powers of two — powers of four are powers of two.)

Those two formulas apply to the starting hex digits 5, 7, 9, and F, counting the number of n hex digit binary/hexadecimal palindromes for each.

Combining the Formulas

The formulas above count the number of n hex digit binary/hexadecimal palindromes by starting hex digit. We can combine them into one pair of formulas that counts all n hex digit binary/hexadecimal palindromes, by adding two copies of the first pair of formulas to four copies of the second pair:

• When n is even: 2·2^n/2-1 + 4·2^n-2 = 2^n/2 + 2ⁿ
• When n is odd: 2·2^(n+1)/2-1 + 4·2^n-1 = 2^(n+1)/2 + 2ⁿ⁺¹

Binary/Hexadecimal Palindromes of n Hexadecimal Digits or Less

To compute the total number of binary/hexadecimal palindromes of n hex digits or less, we need to add together the count of palindromes for each number of digits, 1 through n. We could create a series using the pair of formulas above, but it’s easier to start from scratch: we’ll create a series for each starting digit, and then add them together.

The count of palindromes for each starting digit, from 1 to n digits, is an interleaved sequence — either of nonnegative powers of two or nonnegative powers of four. If you separate those sequences and add their terms — creating series — you’ll have these building blocks, which I’ll use to derive a formula:

• The sum of the first m nonnegative powers of two: = 2^m – 1 .
• The sum of the first m nonnegative powers of four: = (4^m – 1)/3 .

We can use these expressions for each of the interleaved series, adding them together to get expressions that count palindromes of n digits or less by starting digit. We can then combine those expressions to get one pair of formulas — one that counts all palindromes of n digits or less.

Total Palindromes for Each of the Starting Digits 1 and 3

• The number of digits n is even
  The sum consists of two identical series of n/2 terms each:

  = 2^n/2 – 1.

  Added together, they are 2(2^n/2 – 1).

• The number of digits n is odd
  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = 2^(n-1)/2 – 1.

  Added together, they are 2·(2^(n-1)/2 – 1).

  The extra term is 2^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(2^(n-1)/2 – 1) + 2^(n-1)/2, which simplifies to 3·2^(n-1)/2 – 2.

Total Palindromes for Each of the Starting Digits 5, 7, 9, and F

• The number of digits n is even
  The sum consists of two identical series of n/2 terms each:

  = (4^n/2 – 1)/3.

  Added together, they are 2·(4^n/2 – 1)/3.

• The number of digits n is odd
  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = (4^(n-1)/2 – 1)/3.

  Added together, they are 2·(4^(n-1)/2 – 1)/3.

  The extra term is 4^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(4^(n-1)/2 – 1)/3 + 4^(n-1)/2, which simplifies to (5·4^(n-1)/2 – 2)/3.

Total Palindromes for All Digits

To get the total palindromes of n digits or less, we add two copies of the “1/3” pair of formulas to four copies of the “5/7/9/F” pair of formulas:

• The number of digits n is even
  2(2(2^n/2 – 1)) + 4(2(4^n/2 – 1)/3) = 4(2^n/2 – 1) + 8(2ⁿ – 1)/3
• The number of digits n is odd
  2(3·2^(n-1)/2 – 2) + 4((5·4^(n-1)/2 – 2)/3) = 2(3·2^(n-1)/2 – 2) + 4(5·2^n-1 – 2)/3

Summary

Here is a summary of the binary/hexadecimal palindrome counting formulas:

Here’s a table listing the values of these formulas for n = 1 to 16: