Block’n’Role

How low can you go? When it comes to standard bases in mathematics, you can’t go lower than 2. But base 2, or binary, is unsurpassable for simplicity and beauty. With only two digits, 1 and 0, you can capture any integer you like:

• 0, 1, 2, 3, 4, 5... -> 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 101111, 110000, 110001, 110010, 110011, 110100, 110101, 110110, 110111, 111000, 111001, 111010, 111011, 111100, 111101, 111110, 111111...


Here are a few famous decimal numbers in binary:

• 23 = 10111 in binary
• 666 = 1010011010 in binary
• 1492 = 10111010100 in binary
• 2001 = 11111010001 in binary

As you can see, there’s a problem with binary for human beings. It takes up a lot of space and doesn’t look very distinctive. But that’s easy to solve by converting binary into octal (base 8) or hexadecimal (base 16). One digit in octal is worth three digits in binary and one digit in hexadecimal is worth four digits in binary. So the conversion back and forth is very easy:

• 23 = 10111 → (010,111) → 27 in octal
• 23 = 10111 → (0001,0111) → 17 in hexadecimal
• 666 = 1010011010 → (001,010,011,010) → 1232 in octal
• 666 = 1010011010 → (0010,1001,1010) → 29A in hexademical
• 1492 = 10111010100 → (010,111,010,100) → 2724 in octal
• 1492 = 10111010100 → (0101,1101,0100) → 5D4 in hexademical
• 2001 = 11111010001 → (011,111,010,001) → 3721 in octal
• 2001 = 11111010001 → (0111,1101,0001) → 7D1 in hexademical

But there’s another way to compress a binary number: count the lengths of the runs of 1 and 0. For example, 23 = 10111 and 10111 → one 1, one 0, three 1s → (1,1,3) → 113. That’s not much of a compression, but it usually gets better as the numbers get bigger:

• 2001 = 11111010001 → (5,1,1,3,1) → 51131

From the compressed form you can easily re-create the binary number:

• 51131 → (5,1,1,3,1) → (11111,0,1,000,1) → 11111010001

This block-compression doesn’t work with any other standard base. For example, the compressed form (1,2) in ternary, or base 3, is ambiguous:

• (1,2) → (1,00) → 100 in base 3 = 09 in decimal
• (1,2) → (1,22) → 122 in base 3 = 17 in decimal
• (1,2) → (2,00) → 200 in base 3 = 18 in decimal
• (1,2) → (2,11) → 211 in base 3 = 22 in decimal

The higher the base, the bigger the ambiguity. But ambiguity exists with binary block-compressions too. Look at 51131 ← 11111010001 = 2001 in decimal. Out of context, 51131 is infinitely ambiguous. It could represent a number in any base higher than 5:

• 51131 in base 06 = 006751 in base 10
• 51131 in base 07 = 012419 in base 10
• 51131 in base 08 = 021081 in base 10
• 51131 in base 09 = 033643 in base 10
• 51131 in base 10 = 051131 in base 10
• 51131 in base 11 = 074691 in base 10
• 51131 in base 12 = 105589 in base 10
• 51131 in base 13 = 145211 in base 10
• 51131 in base 14 = 195063 in base 10
• 51131 in base 15 = 256771 in base 10
• 51131 in base 16 = 332081 in base 10
• 51131 in base 17 = 422859 in base 10
• 51131 in base 18 = 531091 in base 10
• 51131 in base 19 = 658883 in base 10
• 51131 in base 20 = 808461 in base 10...

But that ambiguity raises an interesting question. Does the binary block-compression of n ever match the digits of n in another base? Yes, it does:

• 23 = 10111 in base 2 → (1,1,3) and 113 in base 4 = 10111 in base 2 = 23 in base 10

113 in base 4 = 1*4^2 + 1*4 + 3*4^0 = 16+4+3 = 23. You could call this “Block’n’Role”, because the blocks of 1 and 0 allow a binary number to retain its identity but take on a different role, that is, represent a number in a different base. Here’s a list of binary block-numbers that match the digits of n in another base:

• 10111 → (1,1,3) = 113 in base 4 (n=23)
• 11001 → (2,2,1) = 221 in base 3 (n=25)
• 101100 → (1,1,2,2) = 1122 in base 3 (n=44)
• 111001 → (3,2,1) = 321 in base 4 (n=57)
• 1011111 → (1,1,5) = 115 in base 9 (n=95)
• 1100001 → (2,4,1) = 241 in base 6 (n=97)
• 11100001 → (3,4,1) = 341 in base 8 (n=225)
• 100110000 → (1,2,2,4) = 1224 in base 6 (n=304)
• 101110111 → (1,1,3,1,3) = 11313 in base 4 (n=375)
• 111111001 → (6,2,1) = 621 in base 9 (n=505)
• 1110010111 → (3,2,1,1,3) = 32113 in base 4 (n=919)
• 10000011111 → (1,5,5) = 155 in base 30 (n=1055)
• 11111100001 → (6,4,1) = 641 in base 18 (n=2017)
• 1011101110111 → (1,1,3,1,3,1,3) = 1131313 in base 4 (n=6007)
• 11100101110111 → (3,2,1,1,3,1,3) = 3211313 in base 4 (n=14711)
• 10111011101110111 → (1,1,3,1,3,1,3,1,3) = 113131313 in base 4 (n=96119)
• 111001011101110111 → (3,2,1,1,3,1,3,1,3) = 321131313 in base 4 (n=235383)
• 100000111111111000001 → (1,5,9,5,1) = 15951 in base 31 (n=1081281)
• 101110111011101110111 → 11313131313 in b4 = 1537911
• 1110010111011101110111 → 32113131313 in b4 = 3766135
• 1011101110111011101110111 → 1131313131313 in b4 = 24606583
• 11100101110111011101110111 → 3211313131313 in b4 = 60258167
• 10111011101110111011101110111 → 113131313131313 in b4 = 393705335
• 111001011101110111011101110111 → 321131313131313 in b4 = 964130679

The list of block-nums is incomplete, because I’ve skipped some trivial examples where, for all powers 2^p > 2^2, the block-num is “1P” in base b = (2^p – p). For example:

• 2^3 = 08 = 1000 in base 2 → (1,3) and 13 in base 5 = 8, where 5 = 2^3-3 = 8-3
• 2^4 = 16 = 10000 in base 2 → (1,4) and 14 in base 12 = 16, where 12 = 2^4-4 = 16-4
• 2^5 = 32 = 100000 in base 2 → (1,5) and 15 in base 27 = 32, where 27 = 2^5-5 = 32-5
• 2^6 = 64 = 1000000 in base 2 → (1,6) and 16 in base 58 = 64, where 58 = 2^6-6 = 64-6

And note that the block-num matches in base 4 continue for ever, because the pairs 113… and 321… generate their successors using simple formulae in base 4:

• 113... * 100 + 13
• 321... * 100 + 13

For example, 113 and 321 are the first pair of matches:

• 10111 → (1,1,3) = 113 in base 4 (n=23)
• 111001 → (3,2,1) = 321 in base 4 (n=57)

In base 4, 113 * 100 + 13 = 11313 and 321 * 100 + 13 = 32113:

• 101110111 → (1,1,3,1,3) = 11313 in base 4 (n=375)
• 1110010111 → (3,2,1,1,3) = 32113 in base 4 (n=919)

Next, 11313 * 100 + 13 = 1131313 and 32113 * 100 + 13 = 3211313:

• 1011101110111 → (1,1,3,1,3,1,3) = 1131313 in base 4 (n=6007)
• 11100101110111 → (3,2,1,1,3,1,3) = 3211313 in base 4 (n=14711)

And so on.