2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ To me this is a strange sequence. You go through (#$5$-$7$) $1100$, $1010$, $1001$ then we need to switch the first digit to $0$, so the "logical" thing to do would be to then go through the progression of three digits (that would make it recursive). However, we cannot do that because we already saw $0100$ in the first four bit strings, so it seems that do get the "right" next step we have to add the 1 for some reason (which seems to rely on previous bit strings). I'm guessing there is a pattern, but it seems a little strange to me whatever it is. $\endgroup$ – Jared Oct 30 '14 at 5:48
  • $\begingroup$ Aye, this pattern emerges because it uses 2 different rules (condition based) to generate the next binary digit from the previous one. Indeed the $a_{n+1}$ term is dependent on the $a_n$ term. I just edited in how I construct the sequence...I apologize if it's not concise. $\endgroup$ – Curator Oct 30 '14 at 5:53
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much! It'll take a little while to digest this, but the effort is appreciated dearly. $\endgroup$ – Curator Oct 30 '14 at 6:06
  • $\begingroup$ No there is a problem with my general solution. I'm not sure I agree that 01101 should be 23 though, $11100$ should be the $16^\text{th}$ value, making 17: 11010, 18: 11001, 19: 01110, 20: 01101. The problem is that there are lots of numbers between $11100$ and $01101$ that we should not have counted. $\endgroup$ – Jared Oct 30 '14 at 6:45
  • $\begingroup$ To be explicit, here is what I assume to be the progression: 1: 10000, 2: 01000, 3: 00100, 4: 00010, 5: 00001 (notice that's $\binom{5}{1} = 5$), 6: 11000, 7: 10100, 8: 10010, 9: 10001, 10: 01100, 11: 01010, 12: 01001, 13: 00110, 14: 00101, 15: 00011 (notice this is $\binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$), then my above progression. $\endgroup$ – Jared Oct 30 '14 at 6:49
  • $\begingroup$ Ahh, yes, you're right, I wasn't going largest to smallest (and was skipping quite a few values), it should have been: 16: 11100, 17: 11010, 18: 11001, 19: 10110, 20: 10101, 21: 10011, 22: 01110, 23: 01101, so that is correct. $\endgroup$ – Jared Oct 30 '14 at 6:57
  • 1
    $\begingroup$ Ok, I deleted my reply, but good to know we are on the same page. I just worked out the progression for n = 5, and reconfirmed that I'm right. Overwise you get less than 31 values. Do you plan on updating your work Jared. If not, would you please leave a few references before you leave for me to study? Regardless, than you very very much. $\endgroup$ – Curator Oct 30 '14 at 7:00
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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