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:
| number | base 2 binary representation |
|---|---|
| one | 1 |
| two | 10 |
| three | 11 |
| four | 100 |
| five | 101 |
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:
| number | base -2 | base i-1 |
|---|---|---|
| one | 1 | 1 |
| two | 110 | 1100 |
| three | 111 | 1101 |
| four | 100 | 111010000 |
| five | 101 | 111010001 |
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.
kunkamath 