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)\,.$$