function from a Binary sequence to the Natural Numbers

Question

I apologize if this is a duplicate question. I don't know enough terminology to thoroughly search.

However, given a sequence of binary numbers $1_10_20_3...0_n$, $0_11_20_3...0_n$, ... , $1_11_20_3...0_n$, $1_10_21_3...0_n$, ... , $1_11_21_3...1_n$ (see below), representing the natural numbers 1, 2, ... n + 1, n + 2, ... $2^n - 1$ respectively, how would I determine the function 'f' taking elements from the above binary sequence to their respective element in the natural sequence?

Thus, I would want a general summation/function that yields 8 for 0110 when n= 4 (similarly yields 23 for 01101 when n = 5).

Example --> for some unknown function 'f' with n = 4 ('f' should work for any n): I generate the values by starting with 1 = 1000. The next value (looped) is either: 1) Set the rightmost 1 to zero, then set the 0 immediately right of this new zero to 1; 2) If the rightmost 1 is in the nth position, I take the largest continuous block of 1's connected to this 1 (length L) and set it back to the 'next' rightmost 1 excluding this block. Then I move ALL L + 1 1's over to the right by 1 term.

$$\begin {array}{r r}f(1000)& 1 \\ f(0100)& 2\\ f(0010) & 3\\ f(0001) & 4\\ f(1100) & 5\\ f(1010) & 6\\ f(1001) & 7\\f(0110) & 8\\ f(0101) & 9\\ f(0011) & 10\\ f(1110) & 11\\ f(1101) & 12\\ f(1011)& 13\\ f(0111) & 14\\ f(1111)& 15 \end {array}$$.

Answer 1

OK, the progression appears to be from "high" to "low" in terms of $1$'s occuring in the bitstring. The lowest occurrences (of $1$'s) appear first. So all you need to do is count the number of $1$'s in your bit string. Then figure out how many came before it, then you can subtract from the highest value of the "substring".

Here is an example:

$$ n = 4, f(1101)= ? $$

There are three $1$'s so we need to find the number of bit strings with either $1$ or $2$ $1$'s first. This is a simple combinatorial problem. You have four distinct objects (the four spots in the bit string) and you need to "choose" $1$ or $2$ of them (by setting their spot to $1$). So the number of previous values is: $\binom{4}{1} + \binom{4}{2} = 4 + 6 = 10$. Now you subtract the maximum possible value with three $1$'s from this value to see where it falls in addition to the previous $1$ or $2$, $1$'s bit strings (don't forget to add 1 since $1110$ would represent the $10 + 1 = 11^\text{th}$ value:

$$ \left(2^3 - 1\right) * 2^{n - 3} - 1101_2 + 1 = 7\cdot2^1 - 13 + 1 = 2 $$

Add that to the previous combinations: $\binom{4}{1} + \binom{4}{2} + 2 = 12$

Computational Complexity: (I don't think this is correct since my general solution is also incorrect)

You can compute these values in $O(n)$ time (the way I described) because the binomial coefficients can be determined successively:

$$ \binom{n}{m + 1} = \frac{n!}{(n - m - 1)!(m+1)!} = \frac{n!(n - m)}{(n - m)!(m+1)m!} = \binom{n}{m}\frac{n - m}{m+1} $$

Which is a variant seen here (the last identity).

General Solution (this is wrong)

Assume that you have already computed the number of $1$'s in your bit string (which can also be done in $O(n)$ time): $s_1(x)$ where $x$ is the bit string in question and $s_1(x)$ is the number of $1$'s occurring in $x$:

\begin{align} f(x) =& \sum_{i = 1}^{i < s_1(x)}\binom{n}{i} + 1 + \left(2^{s_1(x)} - 1\right)2^{n - s_1(x)} - x \\ =&\sum_{i = 1}^{i < s_1(x)}\binom{n}{i} + 1 + 2^n - 2^{n - s_1(x)} - x \\ =&\sum_{i = 1}^{i < s_1(x)}\binom{n}{i} + 2^n\left(1 - \frac{1}{2^{s_1(x)}}\right) - (x - 1) \end{align}

Correction

The problem with the above solution is that it way over counts. As an example take 0111000. I would subtract that from 1110000 getting $7\cdot2^4 - 7\cdot2^3 = 7\cdot2^3\left(2 - 1\right) = 56$, however this difference includes values like 1011111 which is part of a further set (not in the set of "3" $1$'s).

We need to somehow rank the values within a set of known numbers of $1$'s. For instance, $01101$ should be the $8^{\text{th}}$ value with exactly $3$ $1$'s in a $n = 5$ length bit string. We can figure this out by traversing the given bit string:

1. Digit 1: We see a zero, therefore we need to find all of the bit strings of length $5$ with three $1$s for which $1$ occurs in the most significant digit: $\binom{4}{2} = 6$
2. Digit 2: We see a 1, so skip this (this would be the next value if followed by two more 1's)
3. Digit 3: We see a 1, again skip this.
4. Digit 4: We see a zero (but have already seen two 1's), therefore we need to find all of the bit strings of length $5 - 4 = 1$ with zero 1's for which $1$ occurs in the $4^{\text{th}}$ digit, which is $\binom{1}{0} = 1$

Therefore there are $6 + 1 = 7$ values before 01101, which makes 01101 the $8^{\text{th}}$ value containing three $1$'s, added to $\binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$ gives $15 + 8 = 23$.

You can programmatically extend this, but I don't see a simple mathematical formula and I'm not so sure it's $O(n)$ anymore because you are going to have to compute up to $n$ binomial coefficients (which don't have a nice recursive formula necessarily). I do think at worst though it's $O(n^2)$.

Here's another example, the above: 0111000. First you would find $\binom{7}{1} + \binom{7}{2} = 7 + 21 = 28$. Next you would find that a zero is in the first digit, so find $\binom{6}{2} = 15$ to represent all of the ways that the first digit could be $1$ and the next two are in the next $6$ digits. Since the next three digits are all $1$ it would be the next value which is $15 + 1 = 16^\text{th}$, so this value should be the $28 + 16 = 44^\text{th}$ value.

...I'm sure someone cleverer than me can come up with a better solution because I am thinking in terms of brute force here (although giving myself some credit, I do do a little bit better than purely brute force).

Answer 2

Your $f$ in the table given on top is defined via a permutation of the integers on an exponential interval, therefore it can be written as a linear, invertible map given a permutation matrix ($f\leftarrow \Pi\cdot v, v = [1...15]$). What is less trivial is to find the particular permutation. The fundamental property in the table you used appears to be the separation into groups of constant Sum-of-Digits $S_D$. Such groups always correspond to the factorials $N\choose k$for $k=1..N$. This can be found through a recursive procedure in two steps:

A. Produce $S_D(v)$ via the recursion {0} $\rightarrow$ {0,1} $\rightarrow$ {0,1,1,2} $\rightarrow$ {0,1,1,2,1,2,2,3} and so on.

B. Sort resulting vector $u$ ignoring first 0. This will give you the indices of the separate groups ordered according to their increasing $S_D$ from which you can derive the non-zero entries for building $\Pi$.