Prouhet-Thue-Morse Sequence

I was reminded of this sequence when I rewatched a Numberphile YouTube video that related the sequence to the game of chess.

The Prouhet-Thue-Morse is a simple enough sequence but one with many practical applications. It can be described using formal mathematical notation but it can be described in so-called layman's terms as well. This gif from Wikipedia is an example of the latter:

A close look at this gif and it's clear enough how the sequence is being constructed. My last two posts have focussed on recurrence relations and the Prouhet-Thue-Morse sequence can be described more formally as a recurrence relation:$$ \begin{align} t_0 &= 0\\ t_{2n} &= t_n\\ t_{2n+1} &= 1 - t_n \end{align}$$wikiHow has a variety of algorithms for creating the sequence. One uses the recurrence relation as shown in Figure 1:

Figure 1

I incorporated this approach into SageMathCell as shown in Figure 2 (permalink):

Figure 2: permalink

Another approach, what wikiHow calls the Direct Definition, uses the binary form of the natural (decimal) numbers, calculates their binary sum and then uses the modulus 2 of this sum as the output. What's happening is that decimal numbers with an even number of 1's in their binary form are assigned a ZERO and those with an odd number of 1's are assigned a ONE.

\(t_0 = 0 \text{ and } t_n \equiv s_n \bmod{2} \text{ where }s_n \text{ is the binary sum of }n\)

This algorithm is even easier to implement in SageMathCell. See Figure 3 where the output is shown, for variety, as a string rather than a list of elements (permalink):

Figure 2: permalink

The following is an excellent video that I came across from a mathematician who, unconsciously, used the Thue-Morse sequence (sometimes the Prouhet part of the name is omitted) as a child to cope with his obsessive compulsive disorder. Later he describes how he unwittingly used the sequence to solve the Mathematics problem described in Figure 3:

Figure 3

Of course the sequence can be represented with elements other than 0's and 1's. For example, suppose that two persons want to divide an even number of items of equal value between themselves. If the choosing sequence goes ABABABAB ... or BABABABA ... then the person choosing second will always be behind 50% of the time in terms of what they've accumulated. However, using the Thus-Morse sequence, the lead will alternate and in fact represents the fairest way to share things:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABB

Finally, here is a video on the sequence that Stand-up Maths did some years ago: