A Slow-Growing Sequence Defined by an Unusual Recurrence
Fokko J. van de Bult, Dion Gijswijt, John P. Linderman, Neil J.A. Sloane, Allan R. Wilks · arXiv (Cornell University) · 2006
The sequence starts with a(1) = 1; to extend it one writes the sequence so far as XY^k, where X and Y are strings of integers, Y is nonempty and k is as large as possible: then the next term is k. The sequence begins 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, ... A 4 appears for the first time at position 220, but a 5 does not appear until about position 10^{10^{23}}. The main result of the paper is a proof that the sequence is unbounded. We also present results from extensive numerical investigations of the sequence and of certain derived sequences, culminating with a heuristic argument that t (for t=5,6, ...) appears for the first time at about position 2^(2^(3^(4^(5^...^({(t-2)}^{(t-1)}))))), where ^ denotes exponentiation. The final section discusses generalizations.