# Counting Binary and Hexadecimal Palindromes

Copyright © 2008-2014 Exploring Binary

http://www.exploringbinary.com/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:

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 , which is the base 2 version of , 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:

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

= 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

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 .)

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:

= (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:

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

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

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:

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.

December 16th, 2014 at 10:44 pm

[…] Regan presents Counting Binary and Hexadecimal Palindromes posted at Exploring Binary. Rick counts base 10 palindromes as a warm-up before diving into new […]