how do I calculate the Thue-Morse-Sequence over the alphabet {0,1} for $\left(w_{2021}\right)_{2} \bmod 19$?

Question

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.

Answer 1

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...

Answer 2

The formula for inverting an $k$-bit number $x$ is $\bar x = (2^k-1)-x$. So our recurrence formula is $$w_{i+1} = 2^{b_i}w_i + (2^{b_i}-1-w_i) = 2^{b_i}(w_i+1)-(w_i+1) = (2^{b_i}-1)(w_i+1)$$

With $b_i$ the number of bits in the $i$th number. Now this value doubles in binary length each time. So that gives $b_{i+1} = 2b_i$ and taking $m_i:= 2^{b_i}$ we have $m_{i+1} = 2^{2b_i} = (2^{b_i})^2 = m_i^2$. The revised recurrence using $m_i$ is then $w_0=0, m_0=1, w_1=1, m_1 = 2$ and then $$\begin{align}w_{i+1} &= (m_i-1)(w_i+1) \\ m_{i+1} &= m_i^2 \end{align}$$

All these calculations can be done $\bmod 19$. Both $m_i$ and $w_i$ can only have at most $19$ different values$\bmod 19$, so eventually we will have the same pair for both and the overall cycle will close.

In fact, by investigation, $m_i$ settles down into a cycle of length $6$ (starting at $i=2$) and eventually those same residue values for both $m_i$ and $w_i$ $\bmod 19$ occur again at $i=110$, giving an overall $108$ length cycle. So we can simply find the appropriate value in this first cycle matching $2021\bmod 108$ (the cycle length) for the answer.