Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T10:14:09.809Z Has data issue: false hasContentIssue false

Squares and overlaps in the Thue-Morse sequence and some variants

Published online by Cambridge University Press:  18 October 2006

Shandy Brown
Affiliation:
Digital Thinkery, 199 Carter Avenue, Waterloo, Ontario N2J 3K5, Canada; shandy@geeky.net
Narad Rampersad
Affiliation:
School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada; nrampersad@math.uwaterloo.ca; shallit@graceland.uwaterloo.ca; tmjvasiga@cs.uwaterloo.ca
Jeffrey Shallit
Affiliation:
School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada; nrampersad@math.uwaterloo.ca; shallit@graceland.uwaterloo.ca; tmjvasiga@cs.uwaterloo.ca
Troy Vasiga
Affiliation:
School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada; nrampersad@math.uwaterloo.ca; shallit@graceland.uwaterloo.ca; tmjvasiga@cs.uwaterloo.ca
Get access

Abstract

We consider the position and number of occurrences of squaresin the Thue-Morse sequence, and show that the corresponding sequencesare 2-regular. We also prove that changing any finite but nonzeronumber of bits in the Thue-Morse sequence creates an overlap, and anylinear subsequence of the Thue-Morse sequence (except those correspondingto decimation by a power of 2) contains an overlap.

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.)

Article purchase

Temporarily unavailable