Long finite sequences (Q5940305)

Let \(n(k)\) be the length of the longest finite sequence \((x_m)\) in \(k\) letters with the property that no consecutive block \(x_i,\dots,x_{2i}\) is a subsequence of any later block \(x_j,\dots,x_{2j}\). It is shown that \(n(1)=3,\;n(2)=11,\) and a lower bound is given for \(n(3)\) in terms of the Ackermann hierarchy, so that \(n(3)\) may be considered as a description of an incomprehensibly large integer. Asymptotic upper and lower bounds for \(n(k)\) are established, too.