Look And Say Numbers And Conway's Constant
Written by Mike James   
Sunday, 10 August 2014

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?

 johnconway

Banner


RomoCart Brings A Race Track To Your Living Room
11/10/2014

This is a small but innovative project that demonstrates what you can do if you think outside the box - or outside the screen. Is it AR, VR or just reality?



Google APIs Adopt Promises
03/10/2014

Promises seem to be the way that every JavaScript framework is heading. The latest to embrace the Promise is Google's JavaScript Client Library.


More News

 

blog comments powered by Disqus

Last Updated ( Sunday, 10 August 2014 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.