# 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 there exists a set of palindromes and The following table shows all the palindromes for in sorted order. Keep in mind that I will continue to use the 5 bit-system for examples hereon.  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 palindromes, whereby 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 where is the offset from the middle. The catch is that the first elementary palindrome is only a single bit, such as 00100. Therefore The formula is only slightly different for even bit-systems: Now, any palindrome can be written as where 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:  Decimal   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 ! 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 Let’s compute for a 5-bit-system. Now:   Say we want to compute the fifth palindrome. 5 is 101 in binary. Thus Glancing at the above table that result is indeed correct.