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  15Origin/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.
Recurrence formula for a known sequence?
combinatorics;recurrence relation
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$.