Rare binary numbers

Question

Rare numbers are the natural numbers in their binary forms in which there aren't two (or more) ones next to each other. Make a program that will give the N. rare number!

For example:

In case of N = 3 the output will be 4

Here is my trivial solution:

    int nd = Convert.ToInt32(Console.ReadLine());

    int counter = 0;
    int i = 0;
    while (i < nd)
    {

        string binary = Convert.ToString(counter, 2);
        bool founded = false;
        int j = 1;
        while(j < binary.Length && !founded)
        {
            if (binary[j-1] == '1' && binary[j] == '1')
            {
                founded = true;
            }
            j++;
        }
        if (founded == false)
        {
            i++;
        }

        counter++;
    }
    Console.WriteLine(counter -1);

It works, but there must be a smarter and faster way to figure out the solution.

Answer 1

You should do the computation of the "n^th rare number" in a function, so that it is separated from the rest of the program, and can be tested easily:

public static int RareNumber(int n)
{
    // ...      
}

public static void Main()
{
    int n = Convert.ToInt32(Console.ReadLine());
    Console.WriteLine(RareNumber(n));
}

Some feedback with regard to your current code:

• The variable names are confusing. i counts how many rare numbers have been found so far, and counter is the current rare number. founded (or found) does not tell anything about what is found.
• The while-loop can be written more concisely as a for-loop.
• The final subtraction of 1 can be avoided if the number is incremented at the beginning of the loop.
• I would always write if (condition == false) as if (!condition).

Putting it together, the function could look like this:

public static int RareNumber(int nd)
{
    int i = 0; // The current rare number
    int counter = 1; // How many have been found to far
    while (counter < nd)
    {
        i++;
        string binary = Convert.ToString(i, 2);
        bool repeatedOne = false;
        for (var j = 1; j < binary.Length && !repeatedOne; j++)
        {
            if (binary[j-1] == '1' && binary[j] == '1')
            {
                repeatedOne = true;
            }
        }
        if (!repeatedOne)
        {
            counter++;
        }
    }
    return i;
}

The first improvement would be to make the test faster. The conversion from a number to a string is slow. Testing for adjacent "ones" in the binary representation can be done with simple integer arithmetic: A number i is rare exactly if i and i >> 1 have no bit in common:

public static int RareNumber(int n)
{
    int i = 0; // The current rare number
    int counter = 1; // How many have been found to far
    while (counter < n)
    {
        i++;
        if ((i & i >> 1) == 0)
        {
            counter++;
        }
    }
    return i;
}

For even better performance, the "brute-force" approach must be replaced by a more sophisticated algorithm. For these kinds of problems, the On-Line Encyclopedia of Integer Sequences® can be a valuable resource.

If you enter the first rare numbers 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20 into the search field then you'll find A003714 Fibbinary numbers, where a different definition in terms of the Fibonacci numbers is given. There is only a difference by one in the index: Your code computes

R(1) = 0, R(2) = 1, R(3) = 2, R(4) = 4, ...

whereas A003714 has

a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4, ...

From the formula at A003714 one can derive that for \$ n \$ between two consecutive Fibonacci numbers $$ F_k < n \le F_{k+1} $$ we have $$ R(n) = 2^{k-1} + R(n - F_k) \, . $$ (You should make a list with the first 20 rare numbers and convince yourself of the correctness!)

This can be implemented as a recursive function, which should be quite fast because the Fibonacci numbers grow quickly:

public static int RareNumber(int n)
{
    if (n <= 2)
    {
        return n - 1;
    }

    // Two consecutive Fibonacci numbers F(k), F(k+1):
    var f0 = 1;
    var f1 = 2;
    // Corresponding power 2 ** (k-1)
    var p = 1;

    while (f1 < n) {
        // Next pair of Fibonacci numbers:
        var tmp = f0;
        f0 = f1;
        f1 = tmp + f1;
        p <<= 1;
    }
    // Now f0 < n <= f1

    return p + RareNumber(n - f0);
}