# 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 $awawa$, 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 ProuhetThueMorseSequence 2013-03-22 14:27:17 2013-03-22 14:27:17 Mathprof (13753) Mathprof (13753) 24 Mathprof (13753) Definition msc 11B85 msc 68R15 Thue-Morse sequence ProuhetThueMorseConstant