Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T20:02:33.436Z Has data issue: false hasContentIssue false
  • English
  • Français

The Linus Sequence

Published online by Cambridge University Press:  22 June 2009

PAUL BALISTER ,
STEVE KALIKOW  and
AMITES SARKAR
PAUL BALISTER
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected], [email protected])
STEVE KALIKOW
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected], [email protected])
AMITES SARKAR
Affiliation:
Department of Mathematics, Western Washington University, Bellingham, WA 98225, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 1 , January 2010 , pp. 21 - 46
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Allouche, J.-P. and Mendès France, M. (1995) Automata and automatic sequences. In Beyond Quasicrystals (Les Houches 1994), pp. 293–367.CrossRefGoogle Scholar
[2]Christol, G., Kamae, T., Mendès France, M. and Rauzy, G. (1980) Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 401–419.CrossRefGoogle Scholar
[3]Coven, E. and Hedlund, G. (1973) Sequences with minimal block growth. Math. Systems Theory 7 138–153.CrossRefGoogle Scholar
[4]Ehrenfeucht, A. and Mycielski, J. (1992) A pseudorandom sequence: How random is it? Amer. Math. Monthly 99 373–375.Google Scholar
[5]Fine, N. J. and Wilf, H. S. (1965) Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 109–114.CrossRefGoogle Scholar
[6]Jacobs, K. and Keane, M. (1969) 0–1-sequences of Toeplitz type. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 13 123–131.CrossRefGoogle Scholar
[7]Keane, M. (1968) Generalized Morse sequences, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 10 335–353.CrossRefGoogle Scholar
[8]McConnell, T. R. Laws of large numbers for some non-repetitive sequences. barnyard.syr.edu/mseq/mseq.shtml.Google Scholar
[9]Queffélec, M. (1987) Une nouvelle propriété des suites de Rudin–Shapiro. Ann. Inst. Fourier (Grenoble) 37 115–138.CrossRefGoogle Scholar
[10]Queffélec, M. (1995) Spectral study of automatic and substitutive sequences. In Beyond Quasicrystals (Les Houches 1994), pp. 369–414.CrossRefGoogle Scholar
[11]Sutner, K. The Ehrenfeucht–Mycielski sequence. www.cs.cmu.edu/~sutner/papers/em-sequence.pdf.Google Scholar
[12]Weisstein, E. W. Linus sequence. From MathWorld: A Wolfram Web Resource. mathworld.wolfram.com/LinusSequence.html.Google Scholar
[13]Yarlagadda, R. and Hershey, J. E. (1984) Spectral properties of the Thue–Morse sequence. IEEE Trans. Commun. 32 974–977.CrossRefGoogle Scholar