Gijswijt's sequence[1][2] 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 \(10^{10^{23}}\). It has been shown that the sequence is unbounded and, for \(n \geq 5\), the smallest value \(k\) such that \(b(k) = n\) is close to

\[2^{2^{3^{4^{.^{.^{.^{n - 1}}}}}}}.\]

Therefore, the inverse \(c\) of Gijswijt's sequence, defined as minimal \(b(c(n)) = n\), exhibits tetrational growth.

"Gijswitjt's sequence" is pronounced as follows:


Sources Edit

  1. Sloane, Neil. Seven Staggering Sequences
  2. OEIS A090822