Morse sequence

Formation of the first links

The elements of the Morse sequence (also called Morse-Thue sequence , Thue-Morse sequence or Prouhet-Thue-Morse sequence ) are words that are formed from 0 and 1 and are defined as follows: The first element of the sequence is 0. If is the -th sequential term , then the -following term is given by, where from is formed by replacing every 0 by 1 and every 1 by 0. ${\ displaystyle w}$ ${\ displaystyle n}$ ${\ displaystyle (n + 1)}$ ${\ displaystyle ww '}$ ${\ displaystyle w '}$ ${\ displaystyle w}$

Generation of the sequence by substitution

It can also be generated by a substitution algorithm by starting with 0 and replacing a 0 with 01 and a 1 with 10 in each step.

This leads to the sequence 0, 01, 0110, 01101001, ...

Morse sequence as rhythm

The length of the word doubles from sequence member to sequence member because every digit is replaced by two digits.

The corresponding sequence of 0 and 1 is also used as an alternative notation for the sequence:

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

This sequence can also be defined with a semi-thue system . It has close ties to the Gray code .

Morse code is a cube-free language: nowhere does it contain three consecutive identical parts such as 000 or 010101 . If you write the sequence as decimal places of a binary number with 0 in front of the decimal point, you get the Prouhet-Thue-Morse constant (0.01101001… ₂ = 0.412454… - sequence A014571 in OEIS ).

history

The Morse sequence was designed by Marston Morse in 1921 for use in differential geometry. He was not aware of Axel Thue's solution from 1906 or 1912. The earliest mention of this series is found in a short article by Eugène Prouhet on the Prouhet-Tarry-Escott problem , published in 1851. In 1929 there was another independent discovery of the sequence by Max Euwe , who used the cubic freedom to prove the possibility of non-stopping chess games under certain sets of rules.

Web links

Thue-Morse Sequence Article on the Prouhet-Thue-Morse sequence on MathWorld .
Thue-Morse Constant Article on the Prouhet-Thue-Morse constant on MathWorld .
Jean-Paul Allouche, Jeffrey Outlaw Shallit: The Ubiquitous Prouhet-Thue-Morse Sequence . In: Cunsheng Ding, Tor Helleseth, Harald Niederreiter (Ed.): Sequences and Their Applications . Proceedings of SETA '98 . Springer 1999, pp. 1-16.

Individual evidence

^ Marston Morse: Recurrent Geodesics on a Surface of Negative Curvature . Trans. Amer. Math. Soc. Vol. 22 (1921), pp. 84-100.
↑ Axel Thue: About infinite series of characters . Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), pp. 1-22.
↑ Axel Thue: About the mutual position of the same parts of certain series of characters . Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), pp. 1-67.
↑ Eugène Prouhet: Memoir sur quelques relations entre les Puissances of nombres . CR Adad. Sci. Paris . Ser. 1, Vol. 33 (1851), p. 225.
↑ Max Euwe: Set theoretical considerations on the game of chess . Proc. Konin. Akad. Wetenschappen . Vol. 32 (5) (1929), pp. 633-642.

[1] Marston Morse: Recurrent Geodesics on a Surface of Negative Curvature . Trans. Amer. Math. Soc. Vol. 22 (1921), pp. 84-100.

[2] Axel Thue: About infinite series of characters . Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), pp. 1-22.

[3] Axel Thue: About the mutual position of the same parts of certain series of characters . Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), pp. 1-67.

[4] Eugène Prouhet: Memoir sur quelques relations entre les Puissances of nombres . CR Adad. Sci. Paris . Ser. 1, Vol. 33 (1851), p. 225.

[5] Max Euwe: Set theoretical considerations on the game of chess . Proc. Konin. Akad. Wetenschappen . Vol. 32 (5) (1929), pp. 633-642.