Prouhet-Thue-Morse sequence

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


The nth term is defined to be the number of 1s in the binary expansion of n, modulo 2. That is, tn=0 if the number of 1s in the binary expansion of n is even, and tn=1 if it is odd.

The sequence satisfies the following recurrence relation, with t0=0:


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{0,1}, when viewed as a word of infiniteMathworldPlanetmath length over the binary alphabet {0,1}.

Generating function

The generating function T(x)=n=0tnxn for the sequence satisfies the relationMathworldPlanetmath



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


  • Allouche, J.-P.; Shallit, J. O. shallit/Papers/ubiq.psThe ubiquitous Prouhet-Thue-Morse Sequence [postscript]

  • Sloane, N. J. A. Sequence A010060, 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