Fun With Binary Palindromes

Mar 17, 2017 · Gian Sass

My recent vicissitudes have led me into the realm of palindromes. Binary palindromes.

Essentially, palindromes are words or numbers that appear the same when read from left or right. The word “Anna” is a palindrome for example, as well as the number 13931.

But my focus has been primarily on binary palindromic numbers, such as 11011 and 01011010. There is nothing inherently useful about them, though they possess a certain beauty which is only evident to someone who likes to fumble with ones and zeroes.

With the help of a friend I conducted some mindless research concerning the Mathematical properties of these numbers and stumbled upon some things.

The first pattern

For a certain amount of bits $b,$ there exists a set of palindromes $P,$ and $P_n \in \mathbb{Z}.$ The following table shows all the palindromes for $b=5$ in sorted order. Keep in mind that I will continue to use the 5 bit-system for examples hereon. The next thing we asked ourselves was if there lies a sequence behind the pattern of palindromes, or a way to express the nth palindrome?

No.	Binary	Decimal
	00000
1	00100	4
2	01010	10
3	01110	14
4	10001	17
5	10101	21
6	11011	27
7	11111	31

It’s quite easy to notice a pattern: if you glance at the middle column of each number, you find that it repeats the pattern 0 – 1, thus switching state repeatedly. Similarly, the columns directly nearby repeat the pattern 0 – 0 – 1 – 1, and the columns next to those 0 – 0 – 0 – 0 – 1 – 1 – 1 – 1.

So, the farther one is from the middle column, the longer it takes for the bit to toggle. More specifically, the bit-toggle takes place after $2^i$ palindromes, whereby $i$ is the offset from the middle. The same holds for an even amount of bits, where the middle is two bits.

With this knowledge it is easy to devise a program to calculate all palindromes for any amount of bits. The following example is Java code.

int n = 5; /* Amount of bits */
int s = (int)Math.pow(2.0, Math.ceil(n/2.0)); /* Amount of max palindromes */
		
int[] z = new int[s]; /* Array containing palindromes */
		
for(int k = 0; k <= Math.floorDiv(n, 2); k++) {
	int d = (int)Math.pow(2, k);
	for(int i = 0; i < s; i++) {
		int q = Math.floorDiv(i, d);
		if(q%2!=0) {
			if(n%2==0) {
				z[i] |= 1 << (Math.floorDiv(n, 2) - k - 1);
				z[i] |= 1 << (Math.floorDiv(n, 2) + k);
			} else {
				z[i] |= 1 << (Math.floorDiv(n, 2) - k);
				z[i] |= 1 << (Math.floorDiv(n, 2) + k);
			}
		}
	}
}

/* Convert to strings */
String[] strings = new String[s];
for(int i = 0; i < s; i++) {
	strings[i] = Integer.toBinaryString(z[i]);
	int l = strings[i].length();
	if(l != n) {
		for(int j = 0; j < (n-l); j++) {
			strings[i] = "0" + strings[i];
		}
	}
}
		
for(int i = 0; i < s; i++) {
	System.out.println(strings[i]);
}

We need more math!
We now know the algorithm for calculating the set of palindromes for any amount of bits. This leaves us to the next step: a way of expressing the nth palindrome.

Through endless fumbling we realised that each palindrome is the sum of a set of distinctive palindromes in a particular combination. We will call these palindromes elementary palindromes.

Those palindromes have the property of having only two bits set, which are mirrored in the middle, e.g. 01010, 10001, etc. — they are the simplest palindromes in the entire set, and thus it is easy to conclude that every palindrome incorporates them in some way.

For odd bit-systems, they take the form of $e_k = 2^{\left \lfloor{\frac{n}{2}}\right \rfloor- k } + 2^{\left \lfloor{\frac{n}{2}}\right \rfloor + k }$ where $k$ is the offset from the middle. The catch is that the first elementary palindrome is only a single bit, such as 00100. Therefore $e_0 = 2^{\left \lfloor{\frac{n}{2}}\right \rfloor}.$

The formula is only slightly different for even bit-systems: $e_k = 2^{\frac{n}{2} - k - 1} + 2^{\frac{n}{2} + k }.$

Now, any palindrome can be written as $P_n = a_0 e_0 + a_1 e_1 + a_2 e_2 + ...$ where $a_k$ are coefficients that are either zero or one. Each palindrome has its own unique combination of these coefficients. But how can this help us compute the nth palindrome save by chance guessing?

Extending the prior table by the combination of coefficients:

No.	Binary	Decimal	e2	e1	e0
0	00000		0	0	0
1	00100	4	0	0	1
2	01010	10	0	1	0
3	01110	14	0	1	1
4	10001	17	1	0	0
5	10101	21	1	0	1
6	11011	27	1	1	0
7	11111	31	1	1	1

What follows is an interesting pattern: if the coefficients are read like a binary number then that number is equal to $n$ ! This allows for feasible computation of the nth palindrome. The only thing required is to calculate the elementary palindromes and to assign to the coefficients the binary representation of $n.$

Let’s compute for a 5-bit-system. Now:

$e_0 = 2^{\left \lfloor{\frac{5}{2}}\right \rfloor} = 2^{2} = 4.$

$e_1 = 2^{\left \lfloor{\frac{5}{2}}\right \rfloor- 1 } + 2^{\left \lfloor{\frac{5}{2}}\right \rfloor+ 1 } = 10.$

$e_2 = 2^{\left \lfloor{\frac{5}{2}}\right \rfloor- 2 } + 2^{\left \lfloor{\frac{5}{2}}\right \rfloor+ 2 } = 17.$

Say we want to compute the fifth palindrome. 5 is 101 in binary. Thus $P_5 = 1 \times e_0 + 0 \times e_1 + 1 \times e_2 = 1 \times 4 + 0 \times 10 + 1 \times 17 = 21.$ Glancing at the above table that result is indeed correct.