## Introduction

This article provides a method of calculating nth binary palindrome using some math in C# code. I find it useful since all the methods I found using Google had a different approach and were relying on precalculating to array or were using brute force iteration.

## Background

The basic idea for this algorithm is to construct the n^{th} palindrome rather than detect it without a need to construct any other palindrome than the required one.

What I did is I divided each binary palindrome into the left side and right side since one should be the reverse of the other. The following snippet illustrates this division.

---------------Initial Group------------
0
1
---------------Group 0------------------
1|1
101
111
---------------Group 1------------------
10|01
11|11
10001
10101
11011
11111
---------------Group 2------------------
100|001
101|101
110|011
111|111
1000001
1001001
1010101
1011101
1100011
1101011
1110111
1111111
and so on ...

In a snippet above, first, consecutive binary palindromes are divided into groups by the number of digits. In group 0, there are palindromes with 2 and 3 digits, in group 1 palindromes with 4 and 5 digits and so on. For better visualization, I put "|" sign in the middle of palindromes with even digits number.

Now, if we forget about the initial group and group 0 which could be just constants, we can start to think about the algorithm. The first thing that we need to do is to compute in which group our n^{th} element will be. Here, binary logarithm comes in handy:

groupIndex = floor(log2((nth / 3) + 1))

Division by 3 is required here since our group can be divided into 3 sub-groups:

- without digits between sides ('
`|`

' sign is used for ilustration), - with '
`0`

' between sides - with '
`1`

' between sides

Now we can compute number of elements in each sub-group:

subGroupCount = 2 ^ groupIndex

And number of binary palindromes which are before current group (using an adapted sum of geometric sequence formula):

Sum = ((2 ^ groupIndex) - 1) * 3

Let's calculate the index of desired palindrome inside its group:

var insideGroupIndex = nth - Sum;

and the index inside sub-group:

var insideSubGroupIndex = insideGroupIndex % subGroupCount;

Now we can figure out if our binary palindrome has no digit, '`0`

' or '`1`

' between sides (it is an index of a sub group):

var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);

Now we have everything to assemble our palindrome but we have to do it differently for each of 3 sub groups inside a group:

`if (opType == 0)`

left side of a binary palindrome should be `"1" + binaryStringRepresentation(subGroupIndex)`

padded left to digits count in a group. There should be no connector between sides `if (opType == 1)`

left side of a binary palindrome should be `"1" + binaryStringRepresentation(subGroupIndex / 2)`

padded left to digits count in a group. Connector should be '`0`

' or '`1`

' based on if `groupIndex`

is divisible by `2`

(even or odd) `if (opType == 2)`

left side of a binary palindrome should be `"1" + binaryStringRepresentation((subGroupIndex / 2) + (subGroupCount / 2))`

padded left to digits count in a group. Connector should be '`0`

' or '`1`

' based on if `groupIndex`

is divisible by `2`

(even or odd)

Finally, the output should be:

output = leftSide + connector + reverse(leftSide)

## Using the Code

The code for this algorithm looks like this:

private string GetNthBinaryPalindrome(int n)
{
switch (n)
{
case 1:
return "0";
case 2:
return "1";
case 3:
return "11";
case 4:
return "101";
case 5:
return "111";
default:
if (n < 1)
return null;
var S = n - 3;
var groupIndex = (int)Math.Floor(Math.Log((S / 3) + 1, 2));
var digitsCount = group;
var subGroupCount = (int)Math.Round(Math.Pow(2, group));
var Sn = (subGroupCount - 1) * 3;
var insideGroupIndex = S - Sn;
var subGroupIndex = insideGroupIndex % subGroupCount;
var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);
string leftSide;
string connector;
switch (opType)
{
case 0:
connector = "";
leftSide = "1" +
Convert.ToString(subGroupIndex, 2).PadLeft(digitsCount, '0');
break;
case 1:
connector = ((groupIndex & 1) == 0) ? "0" : "1";
leftSide = "1" +
Convert.ToString(subGroupIndex / 2, 2).PadLeft(digitsCount, '0');
break;
case 2:
connector = ((groupIndex & 1) == 0) ? "0" : "1";
leftSide = "1" + Convert.ToString(subGroupIndex / 2 +
subGroupCount / 2, 2).PadLeft(digitsCount, '0');
break;
default:
return null;
}
return String.Format("{0}{1}{2}",
leftSide, connector, String.Join("", leftSide.Reverse()));
}
}

## Points of Interest

This algorithm could be probably even more optimized but for my purposes, it was efficient enough.

## History

- 21
^{st} December, 2016: Initial version - 23
^{st }December, 2016: Corrected typo in palindromes list Group 1