Long Finite Sequences

Let k be a positive integer. There is a longest finite sequence x1, …, xn in k letters in which no consecutive block xi, …, x2i is a subsequence of any later consecutive block xj, …, x2j. Let n(k) be this longest length. We prove that n(1)=3, n(2)=11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackermann hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a particularly elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3).