Look And Say Numbers And Conway's Constant
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


Jumpstart Your Career In Game Development With Udemy
03/11/2016

If you dream about creating the next blockbuster game that goes viral and makes your fortune, Udemy offers two courses that could help you make a start. One introduces the Unity engine while the other [ ... ]



HTML 5.1 Is Here
07/11/2016

When you think back to the days when HTML 5 was the exciting new technology that was going to save us all, it is something of a shock to realize that HTML 5.1 slips in almost unnoticed as an official  [ ... ]


More News

 

 
 
 

blog comments powered by Disqus

Last Updated ( Sunday, 10 August 2014 )
 
 

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