The ubiquitous Prouhet-Thue-Morse sequence. (English) Zbl 1005.11005

Allouche, Jean-Paul; Shallit, Jeffrey

Ding, C. (ed.) et al., Sequences and their applications. Proceedings of the international conference, SETA ’98, Singapore, December 14-17, 1998. London: Springer. Springer Series in Discrete Mathematics and Theoretical Computer Science. 1-16 (1999).

Summary: We discuss a well-known binary sequence called the Thue-Morse sequence, or the Prouhet-Thue-Morse sequence. This sequence was introduced by A. Thue in 1906 (see JFM 39.0283.01) and rediscovered by M. Morse [Recurrent geodesics on a surface of negative curvature, Trans. Am. Math. Soc. 22, 84–100 (1921; JFM 48.0786.06)]. However, it was already implicit in an 1851 paper of Prouhet. The Prouhet-Thue-Morse sequence appears to be somewhat ubiquitous, and we describe many of its apparently unrelated occurrences.
For the entire collection see [Zbl 0974.00035].

MSC:

11B85	Automata sequences
68R15	Combinatorics on words

Keywords:

binary sequence; Thue-Morse sequence