Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Any solution? thanks in advance

share|improve this question
    
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
3  
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
add comment

1 Answer

up vote 2 down vote accepted

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{equation} \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} \end{equation} $$

  • $\forall \;b\; \in S_m^i$: $$ \begin{equation} \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} \end{equation} $$ Where: $$ \begin{equation} \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} \end{equation} $$

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.