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·10^n/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(10^n/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.

Binary Palindromes

Number palindromes have a simple structure: n-digit palindromes are related to n-1 digit palindromes. You can think of generating palindromes as an iterative process, where you start with single-digit palindromes and work your way through palindromes of an increasing number of digits. Here’s an example of the process, using binary numbers:

From the only (nonzero) one-digit palindrome, 1, make the two-digit palindrome 11.
From 11, make the two three-digit palindromes 101 and 111.
From 101, make 1001; from 111, make 1111.
From 1001, make 10001 and 10101; from 1111, make 11011 and 11111.
From 10001, make 100001; from 10101, make 101101; from 11011, make 110011; from 11111 make 111111.
…

From each odd-length palindrome, you can generate one even-length palindrome; you have to replicate the middle digit in order to keep it palindromic. From each even-length palindrome, you can generate two odd-length palindromes, by inserting a 0 or 1 in the middle.

This table illustrates the structure better — it shows all 1 through 8 digit binary palindromes:

**1 to 8-Digit Binary Palindromes (not counting 0)**
Num Digits (n)	Binary Palindromes	Num n-digit Palindromes	Total Palindromes
1	1	1	1
2	11	1	2
3	101 111	2	4
4	1001 1111	2	6
5	10001 10101 11011 11111	4	10
6	100001 101101 110011 111111	4	14
7	1000001 1001001 1010101 1011101 1100011 1101011 1110111 1111111	8	22
8	10000001 10011001 10100101 10111101 11000011 11011011 11100111 11111111	8	30

Counting Binary Palindromes

As typical with things binary, there is a pattern in the palindromes involving powers of two. In this case, it’s easy to see why: each set of odd-length palindromes is double the size of the preceding set of even-length palindromes, and each set of even-length palindromes is the same size as the preceding set of odd-length palindromes. These two formulas capture this relationship, giving the number of n-digit binary palindromes:

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

For n = 1 to 8, you can verify these formulas match the counts in the table: 1, 1, 2, 2, 4, 4, 8, 8.

(The formula can be stated in one expression as $\mbox{\footnotesize{\displaystyle{2^{\lfloor (n-1)/2 \rfloor}}}}$ , which is the base 2 version of $\mbox{\footnotesize{\displaystyle{(b-1) \cdot b^{\lfloor (n-1)/2 \rfloor}}}}$ , the formula stated here. I rewrote it into two parts to remove the slightly cumbersome “floor” function, and to be consistent with the formulas below.)

Number of Binary Palindromes of n Digits or Less

You can further derive a formula for the total number of palindromes of n digits or less, by adding the terms 1, 1, 2, 2, 4, 4, 8, 8, … . Recognizing this sequence as two interleaved sequences of 1, 2, 4, 8, … — that is, sequences of nonnegative powers of two — the derivation of the formula is straightforward.

Here’s the formula to express the sum of the first m nonnegative powers of two:

$\mbox{\footnotesize{\displaystyle{\sum_{i=0}^{m-1}2^i}}}$ = 2^m – 1

We can use this expression for each of the interleaved series, and then add them together. There are two cases:

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}}}$ = 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:

$\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.

For n = 1 to 8, you can verify these formulas match the total counts in the table: 1, 2, 4, 6, 10, 14, 22, 30.

Hexadecimal Palindromes

Using a similar analysis, here are the two formulas to count n-digit hexadecimal palindromes:

When n is even: 15·16^n/2-1
When n is odd: 15·16^(n+1)/2-1

For n = 1 to 8, the value of these formulas is 15, 15, 240, 240, 3840, 3840, 61440, 61440.

(The formula can also be stated in one expression as $\mbox{\footnotesize{\displaystyle{15 \cdot 16^{\lfloor (n-1)/2 \rfloor}}}}$ .)

To count the number of hexadecimal palindromes of n digits or less, we can add series just as we did for binary palindromes. If you factor out 15 from each term in the sequence above, you’re left with this sequence: 1, 1, 16, 16, 256, 256, 4096, 4096. Those are interleaved sequences of nonnegative powers of sixteen.

Here’s the formula to express the sum of the first m nonnegative powers of sixteen:

$\mbox{\footnotesize{\displaystyle{\sum_{i=0}^{m-1}16^i}}}$ = (16^m – 1)/15

We can use this expression for each of the interleaved sequences, and then add them together. There are two cases:

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

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

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

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

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

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

For n = 1 to 8, these formulas return these values: 15, 30, 270, 510, 4350, 8190, 69630, 131070.

Trying These Formulas in PARI/GP

In this section, I’ll demonstrate the formulas for counting binary palindromes, using PARI/GP.

Print the number of 1-digit to 20-digit binary palindromes, using the “floor” form of the expression:

? for (i=1,20,print(2^(floor((i-1)/2))))
1
1
2
2
4
4
8
8
16
16
32
32
64
64
128
128
256
256
512
512

Print the number of 1-digit to 20-digit binary palindromes, using the even and odd case palindrome counting expressions:

? for(i=1,20,if(i%2==1,print(2^((i+1)/2-1)),print(2^(i/2-1))))
1
1
2
2
4
4
8
8
16
16
32
32
64
64
128
128
256
256
512
512

Print the total number of binary palindromes of n digits or less, for n = 1 to 20:

? for(i=1,20,if(i%2==1,print(3*2^((i-1)/2)-2),print(2*(2^(i/2)-1))))
1
2
4
6
10
14
22
30
46
62
94
126
190
254
382
510
766
1022
1534
2046

Summary

Here is a summary of the binary palindrome counting formulas:

**Nonzero Binary Palindrome Counting Formulas**
Num Digits	Even n	Odd n
n	2^n/2-1	2^(n+1)/2-1
n or less	2(2^n/2 – 1)	3·2^(n-1)/2 – 2

Here is a summary of the hexadecimal palindrome counting formulas:

**Nonzero Hexadecimal Palindrome Counting Formulas**
Num Digits	Even n	Odd n
n	15·16^n/2-1	15·16^(n+1)/2-1
n or less	2(16^n/2 – 1)	17·16^(n-1)/2 – 2

Discussion

These formulas can be extended to any base, like octal. (You can see the pattern they follow, although that in itself is not a proof they hold for all bases.)

In my article “Finding Numbers That Are Palindromic In Multiple Bases” I showed how to generate palindromes by iterating through a counter. The analysis of palindromes in this article suggests another algorithm: generating n-digit palindromes from n-1 digit palindromes. (It’s probably not a better way though, at least not for large n, because the required storage space grows exponentially.)

What About Zero?

The number 0 is defined to be a palindrome, although you could make an argument against it. No palindrome can start with zero, yet 0 is a palindrome. In any case, it is not counted in the formulas above, simply because it makes the derivations easier. To count zero, add one to each formula.