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