Thue–Morse sequence

The followers of the Morse sequence ( also Morse - Thue sequence, Thue - Morse sequence or Prouhet - Thue - Morse sequence called ) consist of words that are formed from 0 and 1, and are defined as follows: The first follower is 0 when the follower is th, then the follower is given by where is formed by replacing each 0 through 1, and each 1 by 0.

They can also be produced by a substitution algorithm, by starting with 0, and in each step a 0, a 1 by 01 and replaced by 10.

This results in the sequence 0, 01, 0110, 01101001, ...

The length of the word is doubled by follower to follow-up member, as each digit is replaced by two digits.

The associated sequence of 0 and 1 is used as an alternative spelling of the result:

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ... ( in sequence A010060 OEIS )

This sequence can also be defined by a semi-Thue system. She has close ties to the Gray code.

The Morse sequence is a cubic -free language. They never contain three consecutive identical parts such as 000 or 010101 If we write the result as a decimal to a binary number with a 0 before the decimal point, you get the Prouhet - Thue - Morse constant ( 0.01101001 ... 2 = 0.412454 ... - sequence A014571 in OEIS ).

History

The Morse sequence was constructed by Marston Morse in 1921 for an application in differential geometry .. The solution of Axel Thue from the years 1906 and 1912 was not known to him. The earliest mention of this episode is to be found in a short article by Eugène Prouhet to Prouhet - Tarry - Escott problem, which is published in 1851. 1929, there was another independent discovery of the sequence by Max Euwe, who used the cubic freedom to demonstrate the possibility of non -terminating chess matches in certain rules.