Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.2

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

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


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, $\ldots$ 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, \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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000002 A001511 A010060 A090822 A091408 A091409 A091410 A091411 A091412 A091413 A091579 A091586 A091587 A091588 A001906 A091799 A091839 A091970 A091975 A091976 A092331 A092332 A092333 A092334 A092335 A093914 A093921 A093955 A093956 A093957 A091588 A094006 A094321 A094781 .)

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

Return to Journal of Integer Sequences home page