The Linus Sequence

Source abstract

Define the Linus sequence L n for n ≥ 1 as a 0–1 sequence with L 1 = 0, and L n chosen so as to minimize the length of the longest immediately repeated block L n −2 r +1 ⋅⋅⋅ L n−r = L n−r +1 ⋅⋅⋅ L n . Define the Sally sequence S n as the length r of the longest repeated block that was avoided by the choice of L n . 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.