Define the Linus sequence Ln for n ≥ 1 as a 0–1 sequence with L1 = 0, and Ln chosen so as to minimize the length of the longest immediately repeated block Ln−2r+1 Ln−r = Ln−r+1 Ln. Define the Sally sequence Sn as the length r of the longest repeated block that was avoided by the choice of Ln. We prove several results about these sequences, such as exponential decay of the frequency of highly periodic subwords of the Linus sequence, zero entropy of any stationary process obtained as a limit of word frequencies in the Linus sequence and infinite average value of the Sally sequence. In addition we make a number of conjectures about both sequences.
Combinatorics Probability & Computing
Required Publisher's Statement
Copyright 2010 Cambridge University Press. The original published version of this article may be found at http://dx.doi.org/10.1017/S0963548309990198.
Balister, Paul; Kalikow, Steve; and Sarkar, Amites, "The Linus Sequence" (2010). Mathematics. Paper 4.