On the additive complexity of a Thue-Morse like sequence

Abstract

In this paper, we study the additive complexity ${\rho }_{\mathbf{t}}^{+}(n)$ of a Thue-Morse like sequence $\mathbf{t}={\sigma }^{\infty }(0)$ with the morphism $\sigma :0\to 01,1\to 12,2\to 20$. We show that ${\rho }_{\mathbf{t}}^{+}(n)=2\lfloor {\log }_2(n)\rfloor +3$ for all integers $n\ge 1$. Consequently, $({\rho }_{\mathbf{t}}(n){)}_{n\ge 1}$ is a $2$-regular sequence.

14 pages