Closure aspects of Conway's recursive sequences
by
Jarosław Grytczuk
Technical University of Zielona Góra, Poland

The intriguing recursion C(n)=C(C(n-1))+C(n-C(n-1)), for n > 2 with initial values C(1)=C(2)=1, is attributed mainly to John Conway, who popularized it by offering a cash prize for information on its asymptotic growth. The sequence conceals enormous amount of hidden combinatorial structure, which certainly has not been completely recognized yet. For instance, there is a corresponding set model for C(n), which uses certain linear ordering of finite subsets of integers together with a simple operation of compression. Another possible approach is based on a peculiar operation on words, called Guided Sparse Substitution, which appeared earlier in the work on Cryptosystem Richelieu. In this setting many natural generalizations arise leading to various problems of algebraic and number theoretical nature.

Date received: March 9, 2001