Thue-Morse Constant

The constant also called the Parity Constant and defined by

$\begin{displaymath} P\equiv {\textstyle{1\over 2}}\sum_{n=0}^\infty P(n)2^{-n}=0.4124540336401075977\ldots \end{displaymath}$

(1)

(Sloane's A014571), where

is the Parity of

. Dekking (1977) proved that the Thue-Morse constant is Transcendental, and Allouche and Shallit give a complete proof correcting a minor error of Dekking.

The Thue-Morse constant can be written in base 2 by stages by taking the previous iteration , taking the complement $\overline{a_n}$ , and appending, producing

$\displaystyle a_0$	$\textstyle =$	$\displaystyle 0.0_2$
$\displaystyle a_1$	$\textstyle =$	$\displaystyle 0.01_2$
$\displaystyle a_2$	$\textstyle =$	$\displaystyle 0.0110_2$
$\displaystyle a_3$	$\textstyle =$	$\displaystyle 0.01101001_2$
$\displaystyle a_4$	$\textstyle =$	$\displaystyle 0.0110100110010110_2.$	(2)

This can be written symbolically as

$\begin{displaymath} a_{n+1}=a_n+\overline{a_n}\cdot 2^{-2^n} \end{displaymath}$

(3)

with

. Here, the complement is the number $\overline{a_n}$ such that $a_n+\overline{a_n}=0.\underbrace{11\ldots 1}_{2^n}{}_2$ , which can be found from

$\begin{displaymath} a_n+\overline{a_n}=\sum_{k=1}^{2^n} ({\textstyle{1\over 2}})... ...over 2}})^{2^n}\over 1-{\textstyle{1\over 2}}}-1 = 1-2^{-2^n}. \end{displaymath}$

(4)

Therefore,

$\begin{displaymath} \overline{a_n}=1-2^{-2^n}-a_n, \end{displaymath}$

(5)

and

$\begin{displaymath} a_{n+1}=a_n+(1-2^{-2^n}-a_n) 2^{-2^n}. \end{displaymath}$

(6)

The regular Continued Fraction for the Thue-Morse constant is [0 2 2 2 1 4 3 5 2 1 4 2 1 5 44 1 4 1 2 4 1 1 1 5 14 1 50 15 5 1 1 1 4 2 1 4 1 43 1 4 1 2 1 3 16 1 2 1 2 1 50 1 2 424 1 2 5 2 1 1 1 5 5 2 22 5 1 1 1 1274 3 5 2 1 1 1 4 1 1 15 154 7 2 1 2 2 1 2 1 1 50 1 4 1 2 867374 1 1 1 5 5 1 1 6 1 2 7 2 1650 23 3 1 1 1 2 5 3 84 1 1 1 1284 ...] (Sloane's A014572), and seems to continue with sporadic large terms in suspicious-looking patterns. A nonregular Continued Fraction is

$\begin{displaymath} P={1\over 3-{\strut\displaystyle 1\over\strut\displaystyle 2... ...t\displaystyle 255\over\strut\displaystyle 65536-\ldots}}}}}}. \end{displaymath}$

(7)

A related infinite product is

$\begin{displaymath} 4P=2-{1\cdot 3\cdot 15\cdot 255\cdot 65535\cdots\over 2\cdot 4\cdot 16\cdot 256\cdot 65536\cdots}. \end{displaymath}$

(8)

The Sequence $a_\infty = 0110100110010110100101100\ldots$ (Sloane's A010060) is known as the Thue-Morse Sequence.

See also Rabbit Constant, Thue Constant

References

Allouche, J. P.; Arnold, A.; Berstel, J.; Brlek, S.; Jockusch, W.; Plouffe, S.; and Sagan, B. ``A Relative of the Thue-Morse Sequence.'' Discr. Math. 139, 455-461, 1995.

Allouche, J. P. and Shallit, J. In preparation.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Item 122, Feb. 1972.

Dekking, F. M. ``Transcendence du nombre de Thue-Morse.'' Comptes Rendus de l'Academie des Sciences de Paris 285, 157-160, 1977.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/cntfrc/cntfrc.html

Sloane, N. J. A. Sequences A010060, A014571, and A014572 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.