Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the logic for solving this sequence? [closed]

The sequence goes like this.. 7,8,77,78,87,88,777,778,787,788 and so on..

What can be the logic for finding the nth number of the sequence? I tried that by dividing it by 2 and then by 4 and hence, but it doesn't seem to work.

like image 653
Vaibhav Avatar asked Sep 09 '10 19:09

Vaibhav


2 Answers

Binary, counting from two, ignoring the leading digit, using 7 and 8 for zero and one:

        7,  8,  77,  78,  87,  88,  777,  778,  787,  788
 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011 
like image 185
Pete Kirkham Avatar answered Oct 23 '22 17:10

Pete Kirkham


Observations:

  1. The sequence appears to be an ascending list of numbers containing only the digits 7 and 8.

  2. The number of digits is non-decreasing and for each n-digit section, there are 2 ** n numbers in the sequence.

  3. The first half of the n-digit numbers starts with 7, and the second half starts with 8.

  4. For each half of the n-digit numbers, the remaining digits after the first are the same as the n-1 digit numbers.

These facts can be used to construct a reasonably efficient recursive implementation.

Here is a C# implementation:

void Main() {
    for (int i = 0; i < 10; i++)
        Console.WriteLine (GetSequence(i));
}

string GetSequence(int idx) {
    if (idx == 0) return "7";
    if (idx == 1) return "8";

    return GetSequence(idx / 2 - 1) + GetSequence(idx % 2);
}

Output:

7
8
77
78
87
88
777
778
787
788
like image 15
recursive Avatar answered Oct 23 '22 17:10

recursive