Is there a formula for finding binary numbers in a binary string

binary

One bit

Let's suppose that I have a short binary string: 01. This string contains the binary digits 0 and 1 representing the numbers from zero to one. So, a string 2 digits long is required to represent 2 values (1 bit).

Two bits

That wasn't very interesting. However if I want to represent all the numbers that are up to two bits long in a single string, it's:

00110

This contains:

00 01 10 11

In other words, 5 digits are required to represent 4 values (2 bits).

Three bits

I can do three bits:

0001110100

containing:

000 001 010 011 100 101 110 111

10 digits are required to represent 8 values (3 bits).

Four bits

0000111101100101000

contains all of:

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

19 digits are required to represent 16 values (4 bits).

Additional discovery

Finally I discovered an interesting thing.

Having found my first string for 4 bits 1001010000111101100, I realised I could move a digit from the beginning to the end or vice-versa, and the string would still always contain all the numbers, though sometimes (apparently, half the time) the bit needs to be flipped. So I could do it with:

0010100001111011001
0101000011110110010
1010000111101100101  # this one required flipping the moved digit
0100001111011001010  # this one required flipping the moved digit
1000011110110010100
0000111101100101000  # this one required flipping the moved digit
0001111011001010000 
0011110110010100001  # this one required flipping the moved digit
0111101100101000011  # this one required flipping the moved digit
1111011001010000111  # this one required flipping the moved digit
1110110010100001111
1101100101000011110  # this one required flipping the moved digit
1011001010000111101
0110010100001111011
1100101000011110110
1001010000111101100  # this one required flipping the moved digit

I also realised that this means that if the sequence of digits is looped, I can get away with a shorter sequence. i.e. a repeating 0000111101100101... – 16 digits, still containing all my numbers.

I can lop off two digits from the 3-bit sequence to make 00011101... – 8 digits.

Or remove one digit from the 2-bit sequence to make 0011... – 4 digits.

So if I loop the sequence, it looks like I need as many digits as numbers I can represent in the sequence, while unlooped, it's that number plus the bit-depth minus 1.

But, I am not certain if this holds for 5-bit and higher number rangers, I haven't tried to work that out yet, because so far I haven't yet worked out a sequence for more than 4 bits.

My questions

  • What is the smallest string that would contain all the 5-bit numbers?

  • Is there a formula or process for finding the string, other than intuition and trial-and-error (which is what I used)?

  • Will it always be possible, for any bit-depth, to find a string that contains all the numbers of that bit-depth, without repeating any of them?

  • 1 bit requires 2 digits in the (unlooped) string; 2 bits requires 5; 3 bits requires 10; 4 bits requires 19. Is there a pattern to this and can we know how many digits in the string will be required to contain all the binary numbers of a particular bit-depth?

  • Is there a name for any of this, that I could look up to read more about it?

Best Answer

If you allow wraparound, you need only $2^n$ bits to get all $n$-bit sequences; see De Bruijn sequences. If you don’t allow wraparound, you’ll need to repeat the first $n-1$ bits at the end of the string. For example, $00010111$ does the job with wraparound, while without wraparound you need to extend it to $0001011100$, which yields in turn $000$, $001$, $010$, $101$, $011$, $111$, $110$, and $100$.

In particular, to get all $5$-bit numbers you need $2^5=32$ bits with and $2^5+4=36$ bits without wraparound. One possible sequence is

$$00000100011001010011101011011111(0000)\,.$$

Related Question