Conway Look and Say Sequence--Run Length Encoding

The Conway Sequence is a sequence of digits (also called Look-and-Say sequence) where each term is made of the reading of the digits (the number of consecutive digits) of the previous term. Conway created this sequence as a method of decoding called Run-Length Encoding. RLE is a very basic data compression algorithm that consists in describing a string according to its repetitions. 


How does the Conway Sequence work?

To generate the next term in the sequence, use the previous one, by reading it digit by digit and grouping the numbers that are repeated consecutively. The sequence usually begins with "1" as the first term (also called the "seed). 


Example: The Conway sequence is 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... (and is often used as a riddle where the player must guess the next term).


The sequence with seed 1 contains only the digits 1, 2 and 3.

All terms begin with 1 or 3 except the 3rd.


The sequence grows indefinitely. In fact, any variant defined by starting with a different integer seed number will (eventually) also grow indefinitely, except for the degenerate sequence: 22, 22, 22, 22, … 


No digits other than 1, 2, and 3 appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit.


This is really an exercise in concentration. Also, can you see a pattern in the number of digits with a different starting number?

John Conway is an 82 year old English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He has also contributed to many branches of recreational mathematics, notably the invention of the cellular automaton called the Game of Life. Conway is currently Professor Emeritus of Mathematics at Princeton University in New Jersey.


The attached pdf has the first eight iterations for the seed numbers 1, 2, 22, 10, 123, 333, 789, 1234 as well as answer keys. Additionally, the last page of the pdf has a worksheet for you to choose a seed number of your own and try to make it to the 17th iteration. 




Conway_Look_and_Say_Sequence_Coding.pdf439.53 KB