Prouhet-Thue-Morse sequence

The Prouhet-Thue-Morse sequence is a binary sequence which begins as follows:

$0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,\ldots$

The $n$ th term is defined to be the number of $1$ s in the binary expansion of $n$ , modulo 2. That is, $t_{n}=0$ if the number of $1$ s in the binary expansion of $n$ is even, and $t_{n}=1$ if it is odd.

The sequence satisfies the following recurrence relation, with $t_{0}=0$ :

$\begin{array}[]{ccc}t_{2n}&=&t_{n}\\ t_{2n+1}&=&1-t_{n}\end{array}$

The Prouhet-Thue-Morse sequence is an automatic sequence. It has been shown to be (no three consecutive identical blocks) and overlap-free i.e no sub-block of the form $a w a w a$ , where $a\in\{0,1\}$ , when viewed as a word of infinite length over the binary alphabet $\{0,1\}$ .

Generating function

The generating function $T(x)=\sum_{n=0}^{\infty}t_{n}x^{n}$ for the sequence satisfies the relation

$T(x)=T(x^{2})(1-x)+\frac{x}{1-x^{2}}$

History

The Thue-Morse sequence was independently discovered by P. Prouhet, Axel Thue, and Marston Morse, and has since been rediscovered by many others.

References

•

Allouche, J.-P.; Shallit, J. O. http://www.cs.uwaterloo.ca/ shallit/Papers/ubiq.psThe ubiquitous Prouhet-Thue-Morse Sequence [postscript]
•

Sloane, N. J. A. Sequence A010060, http://www.research.att.com/ njas/sequences/The On-Line Encyclopedia of Integer Sequences.

Title	Prouhet-Thue-Morse sequence
Canonical name	ProuhetThueMorseSequence
Date of creation	2013-03-22 14:27:17
Last modified on	2013-03-22 14:27:17
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	24
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 11B85
Classification	msc 68R15
Synonym	Thue-Morse sequence
Related topic	ProuhetThueMorseConstant