ProuhetThueMorse sequence
The ProuhetThueMorse 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,\mathrm{\dots}$$ 
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}\hfill {t}_{2n}\hfill & \hfill =\hfill & \hfill {t}_{n}\hfill \\ \hfill {t}_{2n+1}\hfill & \hfill =\hfill & \hfill 1{t}_{n}\hfill \end{array}$$ 
The ProuhetThueMorse sequence is an automatic sequence. It has been shown to be (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}^{\mathrm{\infty}}{t}_{n}{x}^{n}$ for the sequence satisfies the relation^{}
$$T(x)=T({x}^{2})(1x)+\frac{x}{1{x}^{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. http://www.cs.uwaterloo.ca/ shallit/Papers/ubiq.psThe ubiquitous ProuhetThueMorse Sequence [postscript]

•
Sloane, N. J. A. Sequence A010060, http://www.research.att.com/ njas/sequences/The OnLine Encyclopedia of Integer Sequences.
Title  ProuhetThueMorse sequence 

Canonical name  ProuhetThueMorseSequence 
Date of creation  20130322 14:27:17 
Last modified on  20130322 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  ThueMorse sequence 
Related topic  ProuhetThueMorseConstant 