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:

Counts of Nonzero, n Hex Digit Binary/Hexadecimal Palindromes
Starting Hex Digit Count From n=1 …
1 1, 1, 2, 2, 4, 4, 8, 8, …
3 1, 1, 2, 2, 4, 4, 8, 8, …
5 1, 1, 4, 4, 16, 16, 64, 64, …
7 1, 1, 4, 4, 16, 16, 64, 64, …
9 1, 1, 4, 4, 16, 16, 64, 64, …
F 1, 1, 4, 4, 16, 16, 64, 64, …

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: 2n/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: 4n/2-1 = 22·(n/2-1) = 2n-2
  • When n is odd: 4(n+1)/2-1 = 22·((n+1)/2-1) = 2n-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·2n/2-1 + 4·2n-2 = 2n/2 + 2n
  • When n is odd: 2·2(n+1)/2-1 + 4·2n-1 = 2(n+1)/2 + 2n+1

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: \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{m-1}2^i}}} = 2m – 1 .
  • The sum of the first m nonnegative powers of four: \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{m-1}4^i}}} = (4m – 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:

    \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{\frac{n}{2}-1}2^i}}} = 2n/2 – 1.

    Added together, they are 2(2n/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:

    \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{\frac{n-1}{2}-1}2^i}}} = 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:

    \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{\frac{n}{2}-1}4^i}}} = (4n/2 – 1)/3.

    Added together, they are 2·(4n/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:

    \mbox{\footnotesize{\displaystyle{\sum_{i=0}^{\frac{n-1}{2}-1}4^i}}} = (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(2n/2 – 1)) + 4(2(4n/2 – 1)/3) = 4(2n/2 – 1) + 8(2n – 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·2n-1 – 2)/3

Summary

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

Nonzero Binary/Hexadecimal Palindrome Counting Formulas
Num Hex Digits Even n Odd n
n 2n/2 + 2n 2(n+1)/2 + 2n+1
n or less 4(2n/2 – 1) + 8(2n – 1)/3 2(3·2(n-1)/2 – 2) + 4(5·2n-1 – 2)/3

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

1-16 Hex Digit Binary/Hexadecimal Palindromes (not counting 0)
Num Hex Digits (n) Num n-digit Palindromes Total Palindromes
1 6 6
2 6 12
3 20 32
4 20 52
5 72 124
6 72 196
7 272 468
8 272 740
9 1056 1796
10 1056 2852
11 4160 7012
12 4160 11172
13 16512 27684
14 16512 44196
15 65792 109988
16 65792 175780
Dingbat
RSS feed icon
RSS e-mail icon

Leave a Reply

Your email address will not be published. Required fields are marked *

(Cookies must be enabled to leave a comment...it reduces spam.)