# Recurrence formula for a known sequence?

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.

• Could you explain somewhat further the motivation for your question? Just tossing a sequence up and vaguely detailing its origin, it seems that you don't really care all that much for an answer. For example, a specific inquiry: how does the minimal number of questions needed to find all the 1s in a binary representation of 0x01 result in the number 7? What is a question, please give a rigorous definition. – Kaya Jul 11 '13 at 3:08
• What's wrong with the closed form that you've already given (the list of 256 values)? – JeffE Jul 11 '13 at 9:33
• And why are any of those numbers bigger than 8? (Is bit 0 equal to 1? Is bit 1 equal to 1? Is bit 2 equal to 1? ...) – JeffE Jul 11 '13 at 9:35
• @Kaya For instance, we have a 8-bit long binary number, say 00000001, then my algorithm would go like this: – kaka Jul 12 '13 at 16:48
• @kaka You should (re)edit your question to ask exactly what you want to know. – Raphael Jul 13 '13 at 12:12

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$.