Gijswijt's sequence

Gijswijt's sequence is a slow-growing integer sequence defined by an unusual recurrence relation named after Dion Gijswijt.
Define \(b(1) = 1\). To find the next term \(b(n + 1)\) of the sequence, express the string \(b(1), b(2), \ldots, b(n)\) as \(XY^k = X\underbrace{Y \ldots Y}_k\), where \(X\) is any string, \(Y\) is any non-empty string, and \(k\) is as large as possible. Then \(b(n + 1) = k\).
The first few terms are 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, ... The first appearance of 3 is at \(b(9)\), and the first 4 does not show up until \(b(220)\). Five does not occur until much later at about \(10^{10^{23.1}}\). It has been shown that the sequence is unbounded and, for \(n \geq 5\), the smallest value \(k\) such that \(b(k) = n\) is conjectured to be approximated as
\[2^{2^{3^{4^{.^{.^{.^{n - 1}}}}}}}.\]
By construction in paper of van de Bult et al. (observation 13), this expression is actually a power tower with height n, where each exponent above the bottom 2, when read upwards, is all consecutive integers from 2 to n-1 (inclusive). If the conjecture is actually correct, then the inverse \(c\) of Gijswijt's sequence, defined as the minimal \(k\) so that \(b(k) = n\), would exhibit tetrational growth.
=== When "4,4" appears ===
Using simple code that exploits the "block-and-glue" structure found in this sequence, it's easy to calculate the first index at which two 4s are adjacent. The first 4 is exactly at index 255895648634818208370064452304769558261700170817472823398081655524438021806620809813295008281436789493636144, which is approximately \(2.5590\times 10^{107}\), and of course the second 4 is immediately after.
== Sources ==
Category:Series
Category:Functions
Category:Eponymous functions
Category:Factorials
Category:Sequences