Fun With Binary Palindromes

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.

n P_n Decimal
0 00000 0
1 00100 4
2 01010 10
3 01110 14
4 10001 17
5 10101 21
6 11011 27
7 11111 31

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?

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:

n P_n Decimal a_2 a_1 a_0
0 00000 0 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.