[Solved]: Recurrence formula for a known sequence?

Problem Detail: 

Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:

1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15

Origin/background of Problem: These number are generated from a divide and conquer algorithm. For example if we have a 8 bit binary-string and we are asked to find the location of 1's in minimal number of questions then, the above sequence is the # of questions asked for each possible binary 8-bit word i.e from 00000000, 00000001 ....11111111 the corresponding # of questions are elements of above sequence i.e 1,7,..15, respectively.

Algorithm:

Lets take 0000 0001, for instance:

1) First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2) Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3) Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4) This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Asked By : kaka

Answered By : Yuval Filmus

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=00010101$. Then the sequence is $$ 0111, 11, 1, $$ and so $N = 6$ and the cost is $13$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13218

3.2K people like this

 Download Related Notes/Documents