Consider the alphabet $\mathcal{A}=\{0,1\}$ and the substitution $\phi$ given by $ \phi(0)=01$, $\phi(1)=10$. Let $t$ be the point given by $t=\lim_{n\rightarrow\infty}\phi^n(0)$. Then $t$ is the Thue-Morse sequence; its first couple of characters are $0110100110010\ldots$.
We define the complexity of a word $u$ as a map $F_u:\mathbb{N}\rightarrow\mathbb{N}$, such that for all $n\in\mathbb{N}$, $F_u(n)$ is equal to the number of distinct subwords of $u$ of length $n$.
Has anyone calculated the complexity function of the Thue-Morse sequence? I have tried to find some sources, but have not succeeded. Any references are most welcome.
According to the French Wikipedia page on the Prouhet-Thue-Morse sequence, the complexity function $c(n)$ of the Thue-Morse sequence is the sequence A005942 on OEIS. It can be computed as follows. For $n \geqslant 1$, let $k \geqslant 0$ be the integer such that $2^k + 1 \leqslant n \leqslant 2^{k + 1}$ and let $r$ be such that $n = 2^k + r$ with $1\leqslant r\leqslant 2^{k}$. Then $$ c(n)= \begin{cases} 3\cdot 2^{k}+4(r-1)&{\text{if }}1 \leqslant r \leqslant 2^{k-1},\\ 4\cdot 2^{k}+2(r-1)&{\text{if }}2^{k-1}+1\leqslant r \leqslant 2^{k}. \end{cases} $$ Moreover, $c(n) \leqslant \frac{10}{3}n$ for all $n$. Relevant references (from the OEIS):
[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003. See Problem 10, p. 335.
[2] J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.
[3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.
[4] A. De Luca, S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), no. 3, 333-348.