# how to formulate the series $1,2,4,8,16,3,5,9,17 …$

Suppose a number is given = $5$ then from the number how to formulate the series -

$1, 2, 4, 8, 16, 3, 5, 9, 17, 6, 10, 18, 12, 20, 24, 7, 13, 21, 11, 19, ...$

actually I want a function of n and the given number m (5 in this case) such that f(1)=1, $f(2) = 2, f(3)=4 ... f(6)=3, f(7) = 5$ like this

Background of the problem : I faced a situation where I needed to find out all possible combination of $5$ digit binary number in a specific order like - $1,10,100,1000,10000,11,101,1001,10001 ....$ i.e. all possible combination of one 1 digit in the $5$ digit precedes all possible combination of two $1$ digit in $5$ digit combination (if possible in the order too) so on

-
Sorry, how is exactly $5$ related to your wonderful sequence? And what is exactly the rule of the sequence? Is it just an arbitrary denumeration of all positive integers? – Berci Nov 2 '12 at 12:19
This seems very closely related to the "combinatorial number system," see en.wikipedia.org/wiki/Combinatorial_number_system – Gerry Myerson Nov 2 '12 at 12:22
Ah, I see now, your sequence will have $31$ numbers (excluding $0$, as I see), and the first $n$ numbers are just the powers of $2$. (Now $n=5$.) – Berci Nov 2 '12 at 12:22
@GerryMyerson +1 Though the information is very useful, but does not quite solve my problem – Diptarag Nov 2 '12 at 12:44

I developed this formulation for the problem, for simplification i ranked the numbers in a decreasing fashion (within a set of numbers with a fixed number of digits set to one) as I didn't get how the local rank mechanism of the original post worked (it starts with a decreasing fashion then deviate from this logic), i reordered the items in a decreasing while being confident about the possibility of formulating other ordering strategies.

Notations:

• The $\sum$ over an empty set is 0

• ${n \choose k}$ is 0 for a negative value of k.

• $d_i(b)$ (or $d_i$ for simplification) is the $i^{th}$ digit of b (it's also the coefficient of $2^{i-1}$ that can be easily formulated as a recursive function of b).

• c(b) is the the number of digits set to 1 in b (easily formulable as a recursive function of b).

• $S_m^i$ is the set of numbers given $c(b)=i$ and $b<2^m$

• $r_l(b)$ is the (local) rank of b within its containing $S_m^i$ (The bigger a number is, smaller is its rank)

• $r_g(b)$ is the (global) rank of the number b.

Properties:

• $card(S_m^i)={m \choose i}$

• If ($c(b)=1$) then $r_g(b)=r_l(b)$

• $\forall$ b given $c(b)\geq2$ we can easily prove that: $$$$\begin{split} r_g(b) =& \sum_{1\leq i\leq c(b)-1} card(S_m^i) + r_l(b)\\ \qquad =& \sum_{1\leq i\leq c(b)-1} {m \choose i} + r_l(b)\\ \end{split}$$$$

• $\forall \;b\; \in S_m^i$: $$$$\begin{split} r_l(b) =& 1 \;+\; \sum_{1\leq j\leq m}{(1-d_{m-j})*{{m-j}\choose {i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})} }}*h_j^i(d)\\ \end{split}$$$$ Where: $$$$\begin{split} h_j^i(d) =&\frac{i-(\sum_{1\leq k\leq j-1}{d_{m-k}})}{max(1\;,\;(i-\sum_{1\leq k\leq j-1}{d_{m-k}}))}\; \end{split}$$$$

The last formula can be intuitively explained as follows: Let d $\in S_m^i$ If the $j^th$ digit (coefficient of $2^{j-1}$) is set to 0, the rank of d is for sure after all the numbers having the $j^{th}$ digit set to 1 and having the same digits configuration as d before this $j^th$ digit. There are ${{m-j} \choose {i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})} }$ ones verifying this last assumption. Why ?

Let's take a closer look :

Assume d = $b_{m-1} b_{m-2} ... b_{j+1} \color{red}{b_j } b_{j-1} ... b_0$

if $\color{red}{b_j } = 0$ then we know that the numbers having the same digit configuration as b before the $j^th$ bit (starting also with $b_{m-1} b_{m-2} ... b_{j+1}$ ) but having $b'_j=1$ are greater than b. How many are they?

First, we know that those numbers still have ${m-j}$ digits at the right of $b'_j$. How many of those remaining digits can be set to one?

Answer : ${i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})}$ because those numbers have already $\sum_{1\leq k\leq j-1}{d_{m-k}}$ digits set to 1, to which we add one as $p_j$ is also set to 1!

However, and here comes the aim of the function h, d should not be penalized by the 0 digits that comes at the right of its last 1 digit. For the simple reason that it is impossible to have other numbers that have digits set to one at this level (Remember that we're on sets of numbers with a fixed number of digits set to 1)

Therefore, we need to define a function that cancels the penalization for those zeros. As soon as j (the sum index) is at the level of those zeros the function takes 0, before that index the function takes 1.

An Example:

10000

01000

00100

00010

00001

11000

10100

10010

10001

01100

01010 -> The rank here is 11.

01001

...

$r_g(01010)={5 \choose 1} + r_l(01010)$

$r_l(01010)=1 + (1-0)*{4 \choose 1}*1 + (1-1)*{3 \choose 1}*1 + (1-0)*{2 \choose 0}*1 + (1-1)*{1 \choose 0}*1 + (1-0)*{0 \choose 0}*0$

$r_l(01010)= 1+ 4 + 0 + 1 + 0 + 0 = 6$

Then : $r_g(01010)= 5 + 6 = 11$

-