Finding nth Binary Palindrome in C#

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