We define the Thue-Morse-Sequence over the alphabet $\Sigma:=\{0,1\}$ as follows: we set $w_{0}:=0$, and for $n \in \mathbb{N}$ we define $w_{n+1}:=w_{n} \overline{w_{n}}$, where $\bar{w}$ is the unit complement of the binary word $w \in \Sigma^{*}$ for example: $\overline{100111}=011000 .$ So the first sequences are: $w_{0}=0, w_{1}=01, w_{2}=0110$, and $w_{3}=01101001$.
Now my question is: how do I calculate $\left(w_{2021}\right)_{2} \bmod 19$?
I can only think of building the whole sequence- but that is obv. impossible. Big thanks in advance for any help regarding my question.
Best Answer
As noted in the comments, we have $w_n+\overline{w_n}=2^{2^n}-1$, so $w_{n+1} = 2^{2^n}\cdot w_n+\overline{w_n}$ $=2^{2^n}\cdot w_n+\left((2^{2^n}-1)-w_n\right)$ $=\left(2^{2^n}-1\right)\cdot(w_n+1)$. For instance, $w_1=1$; $w_2=(2^{2^1}-1)\cdot(1+1) = 3\cdot 2=6$; $w_3=(2^{2^2}-1)\cdot(6+1) = 15\cdot 7=105$; etc. For convenience's sake here I'll write $c_n=2^{2^n}$.
The important thing to notice is that the recursive relation $w_{n+1}=(c_n-1)\cdot(w_n+1)$ only involves additions and multiplications, so for any modulus $t$ we have $w_{n+1}\mod t \equiv \left((c_n-1)\mod t\right)\cdot\left((w_n+1\mod t\right) $ . But there's a nice recursive formula for $c_n$ too: $c_n=(c_{n-1})^2$, and again because this is a multiplication it holds $\mod t$: $c_n\mod t\equiv (c_{n-1}\mod t)^2$. This lets us calculate all the terms using only multiplications of values less than $t$. To illustrate, I'll show how to find the value of the $w_n$ mod $5$ (all the equivalencies here are going to be taken mod $5$):
$$ \begin{align} w_1 = 1&&c_1=4\\ w_2 \equiv (1+1)\cdot(4-1)=6\equiv 1&&c_2=4^2=16\equiv 1\\ w_3 \equiv (1+1)\cdot(1-1)=0\equiv 0&&c_3=1^2\equiv 1\\ w_4 \equiv (0+1)\cdot(1-1)=0\equiv 0&&c_4=1^2\equiv 1\\ \end{align} $$ At this point it should be clear that we have $c_n\equiv 1$ for all $n\geq 2$ and $w_n\equiv 0$ for all $n\geq 3$; all of the $w_n$ turn out to be divisible by $5$. Note that this won't happen mod $19$; the repeated squaring falls into a cycle and never reaches $1$. But the same style of computation will work. Doing it by hand probably isn't worth it, but of course all of these values are easy enough to plug into a computer...