Conway's Cosmological Theorem

The rule for the sequence

1, 11, 21, 1211, 111221, 312211, 13112221, …

is that each term describes the previous one. Start with 1. This can be described as "one one", which can be represented by the digits 11. Now what we have is "two ones", or in digits 21. This in turn is "one two, one one", or 1211. Hence the next term is 1113213211. Of course, one can generate other sequences by the same rule, using different starting points. This generation rule was introduced in 1987 by John Conway, who called it "audioactive decay"; it is also known as "look and say". Henry Bottomley's page about this sequence contains several links to more information. Conway proved some strange and interesting things about these sequences, of which the most impressive was the Cosmological Theorem. The two proofs of this, one by Conway and Richard Parker, and one by Mike Guy (which gave more information), were lost. In 1997, Ekhad and Zeilberger gave a proof that relies on computer verification. It was written for Maple, which I'm not familiar with, so I decided to write my own (in C). In fact I ended up with two programs, both of which verify Guy's sharper version of the theorem, and so may be of interest to someone. You can download:

References

1. J.H. Conway, The weird and wonderful chemistry of audioactive decay, in: Open Problems in Communication and Computation, T.M. Cover and B. Gopinath, eds., Springer, 1987, pp. 173–188.

2. Shalosh B. Ekhad and Doron Zeilberger, Proof of Conway's Lost Cosmological Theorem, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 78–82.