Look and Say Sequence (Conway’s constant)

I just took a look at John Conway’s video at Numberphile about the “look-and-say” sequence or as Conway called it “The Weird and Wonderful Chemistry of Audioactive Decay”. He did a lot of research on this interesting sequence and wrote about it in the Cambridge magazine “Eureka” in 1986.

To see the video, check:

The sequence they are talking about in the video starts with the “seed” 1. So the sequence is thus
1 11 21 1211 111221 312211 13112221 1113213211,…

Conway reveals how to arrive to this sequence in the video, but we can reiterate it very short:

We denote the numbers , where is the step of this “look and say” game. From above we can see that for instance = 312211. To create a new number we need to spell out the number of consecutive numbers in the previous number .

So we start with the seed, which is =1. For we look at and say “that is 1 one” which is 11, so =11. For we look at and see “2 ones” which is 21. becomes “1 two and 1 one” = 1211 and so on.

The sequence is very simple, but tedious to write down by hand. As they mention in the video and as we will see, the sequence will just become longer and longer. To verify Conways constant for yourself, you can write a simple MATLAB script:

function out = lookandsay(in)

in(end+1) = -1; 
%To make the code simple we introduce an
%element that can contrast all other elements in the vector
out = [];

tmp = in(1);
rep = 1;

for i = 2:length(in)

    if in(i) ~= tmp
        out(end+1) = rep;
        out(end+1) = tmp;
        tmp        = in(i);
        rep        = 0;
    end
    
    rep = rep+1;
end

Note that I use arrays of single integers instead of the complete integers, so 12 is [1,2]. I chose to do this because it makes it simpler to add numbers and calculate their length.

That’s it. This function takes one step in the sequence. Beginning with 1, it then produces 11. This is [rep tmp], the number of repetitions of that number and then the number itself. We will denote the sequence for step n. How do we get the other numbers? Well, we can simply start with 1 and update the output vector and feed it back to the function

tmp = [1]; 

for i = 1:10; 
	tmp = lookandsay(tmp) 
end

Conway noticed that the lengths of the vectors in the sequence seem to increase by a constant for each step in the sequence where denotes the number of elements in in step . The constant was named Conway’s constant and it is about 1.3057… in the video he says 1.357 which is wrong.

Remarkably, Conway actually proved that . He found that the constant was the only positive root of …

Hmm, the above polynomial is missing degree 22 and 8… By the way, the constant holds for all seeds except for the seed 22, yeah… seems random. This means that the sequence is strictly increasing in length. However, Conway notices that the sequence can be divided into parts or “elements” and that these sequences are re-occuring. It’s fascinating that such as simple sequence like this could be so complicated to answer.

I’m not going to prove anything about what I have just said. Instead, since we have a program which can create the sequence, we can plot the lengths and calculate the ratios .

tmp = [1]; 
L   = [];
for i = 1:50; 
	tmp  = lookandsay(tmp); 
	L(i) = length(tmp); 
end

We can plot the ratio between the elements in L simply
plot(L(2:end)./L(1:end-1))

The Conway constant convergence using numbers: 1.0000, 2.0000, 1.5000, 1.0000, 1.3333, 1.2500, 1.4000, 1.4286, 1.3000, 1.3077, 1.3529, 1.3478, 1.2581, 1.3077, 1.3137, 1.3134, 1.2841,…

As we can see, the plot slowly converges to 1.3057. After over 30 iterations at which point the length of the vector is 5808 integers long, we eventually start to see that the ratio is converging to this mysterious Conway’s constant.

If you want to read more about the “elements idea” and gain more insight on why the polynomial is so big, see Nathanial Johnstons website.