A new video from Numberphile has John Conway recounting the story of look and say numbers and their interesting properties. It's a story of regularity, but not one that comes from arithmetic. 

John Conway is forever known as the man who invented Life - the cellular automata simulation that produces an incredible richness from incredibly simple rules. He, himself, isn't quite so sure that he wants to be remembered for this one achievement, see Does John Conway Hate Life, and so it is nice to see a video where he explains how he was introduced to, and hence analyzed to death, the phenomenon of look and say numbers. 

I'm not going to tell you what look and say numbers are because in the first few minutes of the video you are challenged to predict the pattern and if you don't know, or if like me you once knew and had forgotten it, then it's really difficult. As a programmer used to thinking about non-arithmetical patterns you might be better placed to get it than the average: 

In case you can't view the video for any reason I'd better say what look and say numbers are:

1) start from 1 and say what you have, i.e one 1.

2) write down what you say as numbers i.e. 11

3) repeat i.e. two 1s and hence 21

Perhaps the quote:

"None of the boys were wearing long party dresses, or if they were, they were not distinguishable from the girls."

also deserves repeating. 

You might well have noticed that look and say numbers are related to run-length coding. Just to remind, you a run length code gives the number of times each symbols is to occur, for example:

3A2B4C 

is the runlength code for 

AAABBCCCC

You can see that a run length code compresses the data as long as on average the runs are greater than two. A look and say sequence generates the next row by run length coding the previous row. What might strike you as remarkable is that the ratio of the lengths of each row tends to 1.303577269... which is known as Conway's constant. This is also the largest and only positive root of a polynomial of degree 71. 

How do you go about proving this? 

Simple, well actually not that simple. All you do is identify the 92 basic "elements" of the sequence, as described in the video, and what they eventually transition to as the sequences grow. This gives you a 92x92 transition matrix and the polynomial in question is the charateristic polynomial of the matrix. 

Any applications?

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info