Binary look-and-say sequences

The first look-and-say sequence most people encounter (if they ever encounter one) is the following:

1
11
21
1211
111221
312211
13112221
1113213211

Take a minute to stare at that sequence. Can you figure out what the next term should be?

At any point in the sequence, one obtains the next term by reading off the number of each digit as it appears in the current term from left-to-right. So, starting with 1 we see “one 1” and we write the second term: 11. Looking at the second term we see “two 1’s” so we write the third term: 21. That term looks like “one 2, one 1” so the next term is 1211. Looking at the last term listed above we see “three 1’s, one 3, one 2, one 1, one 3, one 2, two 1’s” so the next term is 31131211131221. Don’t feel bad if you didn’t see the pattern; Conway missed it too.

A base 2 binary look-and-say

The look-and-say sequence above makes use of the standard decimal system to translate the numbers one, two, and three to their usual digits. In this post I want to look at what happens with different number systems. More precisely, I want to look at a few different binary number systems (i.e. number systems using only two bits 0 and 1 instead of the usual ten digits 0,1,..,9). Let’s start with the standard binary number system, the base 2 binary system. Here’s a table showing how to translate a few numbers in this system:

numberbase 2 binary representation
one1
two10
three11
four100
five101
The standard binary system: base 2

Now, let’s start again with 1 and look-and-say: I see “one 1” so the next term is 11, and now I see “two 1’s” so the next term is 101, and now I see “one 1, one 0, one 1” so we get 111011, and now I see “three 1’s, one 0, two 1’s” so we get 11110101. Here’re the first few terms of this look-and-say sequence:

1
11
101
111011
11110101
100110111011
111001011011110101

Other binary systems

If we use a different base we get different binary representations for numbers. For example, consider the number thirteen. Finding a binary representation of thirteen using base 2 amounts to finding a way to write thirteen as a sum of powers of 2. Well,

13 = 2^3 + 2^2 + 2^0

so the base 2 binary representation of thirteen is 1101. On the other hand, we have

13 = (-2)^4 + (-2)^3 + (-2)^2 + (-2)^0

so the base -2 binary representation of thirteen is 11101. Although it may seem a little strange to use a negative number as a base, there’s nothing stopping us from doing it. In fact, we can even use imaginary bases, like 2i. Since

13 = (2i)^4 + (2i)^2 + (2i)^0

we see that the base 2i binary representation of thirteen is 10101. However, in the binary system with base 2i you cannot represent every natural number (try to write two as a sum of powers of 2i and see what goes wrong!). My favorite binary system uses the complex base i-1. Here’s the key to thirteen for that number system:

13 = (i-1)^8 + (i-1)^4 + (i-1)^0.

Hence the base i-1 binary representation of thirteen is 100010001.

Here is how to translate the numbers one through five using two of the binary systems discussed above:

numberbase -2base i-1
one11
two1101100
three1111101
four100111010000
five101111010001
Nonstandard binary systems

Other binary look-and-says

Using the table above we can write down look-and-say sequences for bases -2 and i-1. Here is one for base -2:

1
11
1101
11011011
1101101101101101
11011011011011011011011011011011

There’s an obvious pattern for that one. Here’s a look-and-say sequence using base i-1:

1
11
11001
110011100011
1100111000110111101011001

Other seeds

So far, all the look-and-see sequences have started with 1, which I’ll call the seed. You get different sequences if you start with different seeds. For example, if we start with 0 we get the following look-and-says:

0
10
1110
3110
132110
1113122110
311311222110
(base 10 decimal)

0
10
1110
11110
100110
1110010110
(base 2 binary)

0
10
1110
111110
101110
1110111110
111110101110
(base -2 binary)

0
10
1110
1101110
110001101110
110011101011001101101110
(base i-1 binary)

The sequences can behave very differently depending on the number systems and the see. For example, try out the look-and-say sequence using the standard decimal system with seed 22, or try the standard binary system with seed 111.

What’s next?

The obvious thing to try to do with these binary sequences is to try to generalize Conway’s results on the standard decimal look-and-say sequences. A nice summary of Conway’s results and the corresponding treatment for the standard binary look-and-say sequence can be found here and here. I’ll describe the analogous treatment for the base -2 binary look-and-says in a future post.

Here are some other possibly interesting directions:

  • Generalize this fun paper for other binary systems.
  • Look into other non-binary look-and-say sequences. The standard ternary story can be found here. What about the ternary system with base -3? What about other number systems with various complex bases and digits?
  • Conway points out that you can write a look-and-say sequence using Roman numerals:
    I
    II
    III
    IIII
    IVI
    IIIVII
    IIIIIVIII
    VIIVIIII
    IVIIIIVIVI
    IIIVIVIIVIIIVII
    IIIIIVIIIVIIIIVIIIIIVIII
    VIIVIIIIIVIVIIVVIIVIIIV
    IVIIIIVVIIVIIIVIIIIIVIIIIVIIIIIV
    IIIVIVIIIVIIIIVIIIIIVVIIVIVIIVVIIV

    I haven’t seen any analysis of this sequence, but I’m guessing someone has worked out what’s going on here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: