You are here
HomeProuhetThueMorse sequence
Primary tabs
ProuhetThueMorse sequence
$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}}&=&1t_{n}\end{array}$ 
The ProuhetThueMorse sequence is an automatic sequence. It has been shown to be cubefree (no three consecutive identical blocks) and overlapfree i.e no subblock 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})(1x)+\frac{x}{1x^{2}}$ 
History
The ThueMorse 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. The ubiquitous ProuhetThueMorse Sequence [postscript]

Sloane, N. J. A. Sequence A010060, The OnLine Encyclopedia of Integer Sequences.
Mathematics Subject Classification
11B85 no label found68R15 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections