What is the logic for solving this sequence?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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 

Answer 6

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

Answer 7

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
                       );