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

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

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

What ca开发者_C百科n 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.

---

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 

---

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

---

Since size of block is growing exponentially (2 elements of length 1, 4 elements of length 2, 8 elements of length 3, etc), you can easily determine number of digits in result number.

    long block_size = 2;
    int len = 1;
    while (n > block_size) {
        n -= block_size;  // n is changed here
        block_size *= 2;
        ++len;
    }

Now, you just create binary representation of n - 1, with 7 for zeroes and 8 for ones (padding it to length len with zeroes). Quite simple.

I assume indexes start from 1 here.

---

substitute 0 for 7 and 1 for 8 and treat it like a binary sequence

---

Written as PHP. I assume that the sequence elements are numbered starting from 1.

$n = 45;
// let's find the 45th sequence element.
$length = 1;
while ( $n >= pow(2, $length + 1) - 1 ) {
    $length++;
}
// determine the length in digits of the sequence element
$offset = $n - pow(2, $length) + 1;
// determine how far this sequence element is past the
// first sequence element of this length
$binary = decbin($offset);
// obtain the binary representation of $offset, as a string of 0s and 1s
while ( strlen($binary) < $length ) {
    $binary = '0'.$binary;
}
// left-pad the string with 0s until it is the required length
$answer = str_replace( array('0', '1'),
                       array('7', '8'),
                       $binary
                       );

---

It looks like a simple binary sequence, where 7 represents binary zero, and 8 represents binary 1.

---

You can compute this directly for the Nth number (num) without recursion or looping by doing the following (the sample code is in MATLAB):

• Compute the number of digits in the number:

  nDigits = floor(log2(num+1));
  

• Find the binary representation of the number num (only the first nDigits digits) after first subtracting one less than two raised to the power nDigits:

  binNum = dec2bin(num-(2^nDigits-1),nDigits);
  

• Add 7 to each value in the string of ones and zeroes:

  result = char(binNum+7);
  

And here's a test, putting the above three steps into one anonymous function f:

>> f = @(n) char(dec2bin(n+1-2^floor(log2(n+1)),floor(log2(n+1)))+7);
>> for n = 1:20, disp(f(n)); end
7
8
77
78
87
88
777
778
787
788
877
878
887
888
7777
7778
7787
7788
7877
7878