Document Type

Article

Publication Date

1-2010

Abstract

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.

Publication Title

Combinatorics Probability & Computing

Volume

19

Issue

1

First Page

21

Last Page

46

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.

Included in

Mathematics Commons

Share

COinS