Editing Thue–Morse sequence (section)

=== 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}}