Binary Babushkas

What’s the connection between grandmothers and this set of numbers?


1, 2, 6, 12, 44, 92, 184, 1208, 1256, 4792, 9912, 19832, 39664, 563952, 576464, 4496112, 4499184, 17996528, 17997488, 143972080, 145057520, 145070832, 294967024, 589944560...

To take the first step towards the answer, you need to put the numbers into binary:


1, 10, 110, 1100, 101100, 1011100, 10111000, 10010111000, 10011101000, 1001010111000, 10011010111000, 100110101111000, 1001101011110000, 10001001101011110000, 10001100101111010000, 10001001001101011110000, 10001001010011011110000, 1000100101001101011110000, 1000100101001111010110000, 1000100101001101011011110000, 1000101001010110011011110000, 1000101001011001101011110000, 10001100101001101011011110000, 100011001010011101011011110000...

The second step is compare those binary numbers with these binary numbers, which represent 1 to 30:


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

To see what’s going on, take the first five numbers from each set:


• 1, 10, 110, 1100, 101100...
• 1, 10, 11, 100, 101...

What’s going on? If you look, you can see the n-th binary number of set 1 contains the digits of all binary numbers <= n in set 2. For example, 101100 is the 5th binary number in set 1, so it contains the digits of the binary numbers 1 to 5:


101100 ← 1
101100 ← 10
101100 ← 11
101100 ← 100
101100 ← 101

Now try 1256 = 10,011,101,000, the ninth number in set 1. It contains all the binary numbers from 1 to 1001:


10011101000 ← 1 (n=1)
10011101000 ← 10 (n=2)
10011101000 ← 11 (n=3)
10011101000 ← 100 (n=4)
10011101000 ← 101 (n=5)
10011101000 ← 110 (n=6)
10011101000 ← 111 (n=7)
10011101000 ← 1000 (n=8)
10011101000 ← 1001 (n=9)

But where do grandmothers come in? They come in via this famous toy:

Nested doll or Russian doll

It’s called a Russian doll and the way all the smaller dolls pack inside the largest doll reminds me of the way all the smaller numbers 1 to 1010 pack into 1001010111000. But in the Russian language, as you might expect, Russian dolls aren’t called Russian dolls. Instead, they’re called matryoshki (матрёшки, singular матрёшка), meaning “little matrons”. However, there’s a mistaken idea in English that in Russian they’re called babushka dolls, from Russian бабушка, babuška, meaning “grandmother”. And that’s what I thought, until I did a little research.

But the mistake is there, so I’ll call these babushka numbers or grandmother numbers:


1, 2, 6, 12, 44, 92, 184, 1208, 1256, 4792, 9912, 19832, 39664, 563952, 576464, 4496112, 4499184, 17996528, 17997488, 143972080, 145057520, 145070832, 294967024, 589944560...

They’re sequence A261467 at the Online Encyclopedia of Integer Sequences. They go on for ever, but the biggest known so far is 589,944,560 = 100,011,001,010,011,101,011,011,110,000 in binary. And here is that binary babushka with its binary babies:


100011001010011101011011110000 ← 1 (n=1)
100011001010011101011011110000 ← 10 (n=2)
100011001010011101011011110000 ← 11 (n=3)
100011001010011101011011110000 ← 100 (n=4)
100011001010011101011011110000 ← 101 (n=5)
100011001010011101011011110000 ← 110 (n=6)
100011001010011101011011110000 ← 111 (n=7)
100011001010011101011011110000 ← 1000 (n=8)
100011001010011101011011110000 ← 1001 (n=9)
100011001010011101011011110000 ← 1010 (n=10)
100011001010011101011011110000 ← 1011 (n=11)
100011001010011101011011110000 ← 1100 (n=12)
100011001010011101011011110000 ← 1101 (n=13)
100011001010011101011011110000 ← 1110 (n=14)
100011001010011101011011110000 ← 1111 (n=15)
100011001010011101011011110000 ← 10000 (n=16)
100011001010011101011011110000 ← 10001 (n=17)
100011001010011101011011110000 ← 10010 (n=18)
100011001010011101011011110000 ← 10011 (n=19)
100011001010011101011011110000 ← 10100 (n=20)
100011001010011101011011110000 ← 10101 (n=21)
100011001010011101011011110000 ← 10110 (n=22)
100011001010011101011011110000 ← 10111 (n=23)
100011001010011101011011110000 ← 11000 (n=24)
100011001010011101011011110000 ← 11001 (n=25)
100011001010011101011011110000 ← 11010 (n=26)
100011001010011101011011110000 ← 11011 (n=27)
100011001010011101011011110000 ← 11100 (n=28)
100011001010011101011011110000 ← 11101 (n=29)
100011001010011101011011110000 ← 11110 (n=30)

Babushka numbers exist in higher bases, of course. Here are the first thirteen in base 3 or ternary:


1 contains 1 (c=1) (n=1)
12 contains 1, 2 (c=2) (n=5)
102 contains 1, 2, 10 (c=3) (n=11)
1102 contains 1, 2, 10, 11 (c=4) (n=38)
10112 contains 1, 2, 10, 11, 12 (c=5) (n=95)
101120 contains 1, 2, 10, 11, 12, 20 (c=6) (n=285)
1021120 contains 1, 2, 10, 11, 12, 20, 21 (c=7) (n=933)
10211220 contains 1, 2, 10, 11, 12, 20, 21, 22 (c=8) (n=2805)
100211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100 (c=9) (n=7179)
10021011220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101 (c=10) (n=64284)
1001010211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102 (c=11) (n=553929)
1001011021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110 (c=12) (n=554253)
10010111021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111 (c=13) (n=1663062)

Look at 1,001,010,211,220 (n=553929) and 1,001,011,021,220 (n=554253). They have the same number of digits, but the babushka 1,001,011,021,220 manages to pack in one more baby:


1001010211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102 (c=11) (n=553929)
1001011021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110 (c=12) (n=554253)

That happens in binary too:


10010111000 contains 1, 10, 11, 100, 101, 110, 111, 1000, 1001 (c=9) (n=1208)
10011101000 contains 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 (c=10) (n=1256)

What happens in higher bases? Watch this space.