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:

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: 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^{n} - When n is odd: 2·2
^{(n+1)/2-1}+ 4·2^{n-1}= 2^{(n+1)/2}+ 2^{n+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: = 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^{n}– 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:

Num Hex Digits | Even n | Odd n |
---|---|---|

n | 2^{n/2} + 2^{n} |
2^{(n+1)/2} + 2^{n+1} |

n or less | 4(2^{n/2} – 1) + 8(2^{n} – 1)/3 |
2(3·2^{(n-1)/2} – 2) + 4(5·2^{n-1} – 2)/3 |

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

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 |