This program generates the Look and Say sequence of integers. This is the sequence of integers beginning

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211

As you can see, these things grow real fast. The seventieth one has 179,691,598 digits.

The program can generate the sequence in bases two through sixteen. Note that this is different than just printing out the sequence in these bases due to the way the sequence is defined. However, the sequence is the same in all bases greater than three, so the only bases that are significant are two, three, and all the others.

There are many interesting things to think about with this sequence. One first question is whether it grows indefinitely. The numbers certainly seem to be getting larger, but this does not have to be the case. If we were ever to arrive at the number 11111, for example, the next number would be 51. In fact, there is a cycle the numbers could enter: 22. As it turns out, that is the only one. A Look and Say sequence beginning with any other number will in fact grow indefinitely.

When considering these numbers in class the other day, I wrote out a bunch of them and guessed that they grow asymptotic to eⁿ². In fact, they grow asymptotic to e^en. You can see this with the help of two programs included in the tarball: dif and log. The first takes each line of its input and subtracts the previous line, printing the result. That is, it differentiates its input. The second just prints the number of digits in each line of its input; that is, it takes the log. Try running ./lookandsay | perl log | perl log | perl dif. Note that you get (essentially) constant output.

To be precise, the sequence grows asymptotic to 10^Cn, where C and are constants. The constant = 1.303577269... is called Conway's constant and is (astonishingly) the one positive, real root of a particular polynomial of degree seventy-one.

That would be interesting enough, but it gets much better. It turns out that numbers in the Look and Say sequence contain "substrings" of digits that grow independent of the rest of the digits. That is, in subsequent members of the sequence, the rest of the digits are never affected. One (non-growing) example of such a pattern is 22.

These patterns are called "elements", and groups of them are called "compounds". There are 92 elements that were discovered by Conway and are particular noteworthy. These elements "decay" into one another. All of them eventually show up in any Look and Say sequence starting from any number, and every sequence eventually comes to be either composed entirely of these 92 elements or increasingly dominated by them. Here you can see a graph that depicts how the 92 elements decay into one another.

Oops, looks like I missed another class writing this. I really need to get better about going to class.