Prouhet-Thue-Morse sequence


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

0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,

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:

t2n=tnt2n+1=1-tn

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

T(x)=T(x2)(1-x)+x1-x2

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