Editing Thue–Morse sequence (section)

== Definition ==
There are several equivalent ways of defining the Thue–Morse sequence.

=== Direct definition ===
[[File:Thue-Morse binary digit sum.svg|thumb|128px|When counting in binary, the digit sum modulo 2 is the Thue–Morse sequence]]

To compute the ''n''th element ''t<sub>n</sub>'', write the number ''n'' in [[Binary number|binary]].  If the [[Hamming weight|number of ones]] in this binary expansion is odd then ''t<sub>n</sub>''&nbsp;=&nbsp;1, if even then ''t<sub>n</sub>''&nbsp;=&nbsp;0.<ref name=AS15>{{harvtxt|Allouche|Shallit|2003|p=15}}</ref>  That is, ''t<sub>n</sub>'' is the [[parity bit|even parity bit]] for ''n''. [[John H. Conway]] ''et al''. deemed numbers ''n'' satisfying ''t<sub>n</sub>''&nbsp;=&nbsp;1 to be ''odious'' (intended to be similar to ''odd'') numbers, and numbers for which ''t<sub>n</sub>''&nbsp;=&nbsp;0 to be ''evil'' (similar to ''even'') numbers.

=== Fast sequence generation ===
This method leads to a fast method for computing the Thue–Morse sequence: start with {{math|1=''t''<sub>0</sub>&nbsp;=&nbsp;0}}, and then, for each ''n'', find the highest-order bit in the binary representation of ''n'' that is different from the same bit in the representation of {{math|1=''n''&nbsp;&minus;&nbsp;1}}. If this bit is at an even index,  ''t<sub>n</sub>'' differs from {{math|1=''t''<sub>''n''&nbsp;&minus;&nbsp;1</sub>}}, and otherwise it is the same as {{math|1=''t''<sub>''n''&nbsp;&minus;&nbsp;1</sub>}}.

In [[Python (programming language)|Python]]:
<syntaxhighlight lang="python">
def generate_sequence(seq_length: int) -> int:
    """Thue–Morse sequence."""
    value: int = 1
    for n in range(seq_length):
        # Note: assumes that (-1).bit_length() gives 1
        x: int = (n ^ (n - 1)).bit_length() + 1
        if x & 1 == 0:
            # Bit index is even, so toggle value
            value = 1 - value
        yield value
</syntaxhighlight>
The resulting algorithm takes constant time to generate each sequence element, using only a [[L (complexity)|logarithmic number of bits]] (constant number of words) of memory.{{sfnp|Arndt|2011}}

=== Recurrence relation ===
The Thue–Morse sequence is the sequence ''t<sub>n</sub>'' satisfying the [[recurrence relation]]

:<math>\begin{align}
   t_0 &= 0,\\
   t_{2n} &= t_n,\\
   t_{2n+1} &= 1 - t_n,
 \end{align}</math>

for all non-negative integers ''n''.<ref name=AS15/>

=== L-system ===
[[File:Thue-Morse L-System.svg|thumb|256px|Thue–Morse sequence generated by an L-System]]

The Thue–Morse sequence is a [[morphic word]]:<ref>{{harvtxt|Lothaire|2011|p=11}}</ref> it is the output of the following [[L-system|Lindenmayer system]]:
{| class="wikitable"
|-
! Variables <td> 0, 1 </td>
|-
! Constants <td> None </td>
|-
! Start <td> 0 </td>
|-
! Rules <td> (0 → 01), (1 → 10) </td>
|}

=== Characterization using bitwise negation ===
The Thue–Morse sequence in the form given above, as a sequence of [[bit]]s, can be defined [[recursion|recursively]] using the operation of [[bitwise negation]].
So, the first element is 0.
Then once the first 2<sup>''n''</sup> elements have been specified, forming a string ''s'', then the next 2<sup>''n''</sup> elements must form the bitwise negation of ''s''.
Now we have defined the first 2<sup>''n''+1</sup> elements, and we recurse.

Spelling out the first few steps in detail:
* We start with 0.
* The bitwise negation of 0 is 1.
* Combining these, the first 2 elements are 01.
* The bitwise negation of 01 is 10.
* Combining these, the first 4 elements are 0110.
* The bitwise negation of 0110 is 1001.
* Combining these, the first 8 elements are 01101001.
* And so on.

So
* ''T''<sub>0</sub> = 0.
* ''T''<sub>1</sub> = 01.
* ''T''<sub>2</sub> = 0110.
* ''T''<sub>3</sub> = 01101001.
* ''T''<sub>4</sub> = 0110100110010110.
* ''T''<sub>5</sub> = 01101001100101101001011001101001.
* ''T''<sub>6</sub> = 0110100110010110100101100110100110010110011010010110100110010110.
* And so on.

In [[Python (programming language)|Python]]:
<syntaxhighlight lang="python">
def thue_morse_bits(n):
	"""Return an int containing the first 2**n bits of the Thue-Morse sequence, low-order bit 1st."""
	bits = 0
    for i in range(n):
        bits |= ((1 << (1 << i)) - 1 - bits) << (1 << i)
    return bits
</syntaxhighlight>

Which can then be converted to a (reversed) string as follows: 
<syntaxhighlight lang="python">
n = 7
print(f"{thue_morse_bits(n):0{1<<n}b}")
</syntaxhighlight>

=== Infinite product ===
The sequence can also be defined by:
: <math> \prod_{i=0}^{\infty} \left(1 - x^{2^i}\right) = \sum_{j=0}^{\infty} (-1)^{t_j} x^j,</math>
where ''t''<sub>''j''</sub> is the ''j''th element if we start at ''j'' = 0.