A Slow-Growing Sequence Defined by an Unusual Recurrence

The sequence starts with

; to extend it one writes the sequence so far as

, where

and

are strings of integers,

is nonempty and

is as large as possible: then the next term is

. The sequence begins 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, $\ldots$ A

appears for the first time at position 220, but a

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

(for $t=5,6, \ldots$ ) appears for the first time at about position $2\uparrow (2\uparrow (3\uparrow (4\uparrow (5\uparrow \ldots \uparrow ({(t-2)}\uparrow {(t-1)})))))$ , where $\uparrow$ denotes exponentiation. The final section discusses generalizations.

Received February 22 2006; revised version received September 13 2006. Published in Journal of Integer Sequences December 16 2006.

A Slow-Growing Sequence Defined by an Unusual Recurrence

Fokko J. van de Bult and Dion C. Gijswijt Korteweg-de Vries Institute for Mathematics University of Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam Netherlands John P. Linderman, N. J. A. Sloane and Allan R. Wilks AT&T Shannon Labs 180 Park Avenue Florham Park, NJ 07932-0971 USA

Fokko J. van de Bult and Dion C. Gijswijt
Korteweg-de Vries Institute for Mathematics
University of Amsterdam
Plantage Muidergracht 24
1018 TV Amsterdam
Netherlands

John P. Linderman, N. J. A. Sloane and Allan R. Wilks
AT&T Shannon Labs
180 Park Avenue
Florham Park, NJ 07932-0971
USA