Thue-Morse

Thue-Morse
You are encouraged to solve this task according to the task description, using any language you may know.

Task

Create a Thue-Morse sequence.

See also

•   YouTube entry: The Fairest Sharing Sequence Ever
•   YouTube entry: Math and OCD - My story with the Thue-Morse sequence
•   Task: Fairshare between two and more

11l

Translation of: Python: By counting set ones in binary representation

F thue_morse_digits(digits)
   R (0 .< digits).map(n -> bits:popcount(n) % 2)

print(thue_morse_digits(20))

Output:

[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

8080 Assembly

The 8080 processor has an internal flag to keep track of the parity of the result of the last operation. This is ideal for generating the Thue-Morse sequence, as one can just count up by incrementing a register, and then check the parity each time. If the parity is even, the corresponding element in the Thue-Morse sequence is 0, if it is odd it is 1. You can even use the same register to iterate over the array where you're storing the elements, and get the parity calculation entirely for free.

Unfortunately, this flag was not deemed very useful otherwise, and in the Z80 support for it was dropped and replaced with a signed overflow flag. This is one of the few places where the Z80 is not backwards compatible with the 8080. This does mean that the binary produced by assembling this program will only run correctly on a real 8080 (or a proper 8080 emulator).

The following program prints the first 256 elements of the Thue-Morse sequence, since that fits neatly in an 8-bit register, but the same principle could be used with a counter of arbitrary size, as after all, XOR is commutative.

	org	100h
	;;;	Write 256 bytes of ASCII '0' starting at address 200h
	lxi	h,200h	; The array is page-aligned so L starts at 0
	mvi	a,'0'	; ASCII 0
zero:	mov	m,a	; Write it to memory at address HL
	inr	l	; Increment low byte of pointer, 
	jnz	zero	; until it wraps to zero.
	;;;	Generate the first 256 elements of the Thue-Morse sequence.
gen:	jpe	$+4	; If parity is even, skip next instruction
	inr	m	; (If parity is odd,) increment byte at HL (0->1) 
	inr	l	; Increment low byte of pointer (and set parity),
	jnz	gen	; Until it wraps again. 
	;;;	Output using CP/M call
	inr	h	; Increment high byte,
	mvi	m,'$'	; and write the CP/M string terminator there.
	mvi	c,9	; Syscall 9 = print string
	lxi	d,200h	; The string is at 200h
	jmp	5

Output:

The line breaks are added for clarity, the program does not actually print them.

0110100110010110100101100110100110010110011010010110100110010110
1001011001101001011010011001011001101001100101101001011001101001
1001011001101001011010011001011001101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Action!

PROC Next(CHAR ARRAY s)
  BYTE i,len
  CHAR c

  IF s(0)=0 THEN
    s(0)=1 s(1)='0
    RETURN
  FI

  FOR i=1 TO s(0)
  DO
    IF s(i)='0 THEN
      c='1
    ELSE
      c='0
    FI
    s(s(0)+i)=c
  OD
  s(0)==*2
RETURN

PROC Main()
  BYTE i
  CHAR ARRAY s(256)

  s(0)=0
  FOR i=0 TO 7
  DO
    Next(s)
    PrintF("T%B=%S%E%E",i,s)
  OD
RETURN

Output:

Screenshot from Atari 8-bit computer

T0=0

T1=01

T2=0110

T3=01101001

T4=0110100110010110

T5=01101001100101101001011001101001

T6=0110100110010110100101100110100110010110011010010110100110010110

T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Ada

Implementation using an L-system.

with Ada.Text_IO; use Ada.Text_IO;

procedure Thue_Morse is
   
   function Replace(S: String) return String is
      -- replace every "0" by "01" and every "1" by "10"
      (if S'Length = 0 then "" 
      else (if S(S'First) = '0' then "01" else "10") & 
	Replace(S(S'First+1 .. S'Last)));
      
   function Sequence (N: Natural) return String is
      (if N=0 then "0" else Replace(Sequence(N-1)));   
      
begin
   for I in 0 .. 6 loop
      Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I));
   end loop;
end Thue_Morse;

Output:

 0: 0
 1: 01
 2: 0110
 3: 01101001
 4: 0110100110010110
 5: 01101001100101101001011001101001
 6: 0110100110010110100101100110100110010110011010010110100110010110

ALGOL 68

# "flips" the "bits" in a string (assumed to contain only "0" and "1" characters) #
OP  FLIP = ( STRING s )STRING:
    BEGIN
        STRING result := s;
        FOR char pos FROM LWB result TO UPB result DO
            result[ char pos ] := IF result[ char pos ] = "0" THEN "1" ELSE "0" FI
        OD;
        result
    END; # FLIP #

# print the first few members of the Thue-Morse sequence #
STRING tm := "0";
TO 7 DO
    print( ( tm, newline ) );
    tm +:= FLIP tm
OD

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

APL

⍝ generate the first ⍵ elements of the Thue-Morse sequence
tm←{⍵⍴(⊢,~)⍣(⍵≤(⍴⊢))⊢,0}

Output:

      tm 32
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

AppleScript

Functional

Translation of: JavaScript

------------------------ THUE MORSE ----------------------

-- thueMorse :: Int -> String
on thueMorse(nCycles)
    script concatBinaryInverse
        on |λ|(xs)
            script binaryInverse
                on |λ|(x)
                    1 - x
                end |λ|
            end script
            
            xs & map(binaryInverse, xs)
        end |λ|
    end script
    
    intercalate("", ¬
        foldl(concatBinaryInverse, [0], ¬
            enumFromTo(1, nCycles)))
end thueMorse


--------------------------- TEST -------------------------
on run
    
    thueMorse(6)
    
    --> 0110100110010110100101100110100110010110011010010110100110010110
end run


------------------------- GENERIC ------------------------

-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
    if m ≤ n then
        set lst to {}
        repeat with i from m to n
            set end of lst to i
        end repeat
        lst
    else
        {}
    end if
end enumFromTo


-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl


-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
    set {dlm, my text item delimiters} to {my text item delimiters, strText}
    set strJoined to lstText as text
    set my text item delimiters to dlm
    return strJoined
end intercalate


-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map


-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

"0110100110010110100101100110100110010110011010010110100110010110"

---

Idiomatic

Implements the "flip previous cycles" method, stopping at a specified sequence length.

on ThueMorse(sequenceLength)
    if (sequenceLength < 1) then return ""
    
    script o
        property sequence : {0}
    end script
    
    set counter to 1
    set cycleEnd to 1
    set i to 1
    repeat until (counter = sequenceLength)
        set end of o's sequence to ((item i of o's sequence) + 1) mod 2
        set counter to counter + 1
        if (i < cycleEnd) then
            set i to i + 1
        else
            set i to 1
            set cycleEnd to counter
        end if
    end repeat
    
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to ""
    set sequence to o's sequence as text
    set AppleScript's text item delimiters to astid
    
    return sequence
end ThueMorse

return linefeed & ThueMorse(64) & (linefeed & ThueMorse(65))

Output:

"
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101"

Arturo

thueMorse: function [maxSteps][
    result: new []
    val: [0]
    count: new 0
    while [true][
        'result ++ join to [:string] val
        inc 'count
        if count = maxSteps -> return result
        val: val ++ map val 'v -> 1 - v
    ]
    return result
]
loop thueMorse 6 'bits ->
    print bits

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001

AutoHotkey

ThueMorse(num, iter){
	if !iter
		return num
	for i, n in StrSplit(num)
		opp .= !n
	res := ThueMorse(num . opp, --iter)
	return res
}

Examples:

num := 0
loop 7
	output .= A_Index-1 " : " ThueMorse(num, A_Index-1) "`n"
MsgBox % output

Output:

0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110

AWK

BEGIN{print x="0"}
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}

BASIC

BASIC256

Translation of: FreeBASIC

tm = "0"

Function Thue_Morse(s)
	k = ""
	For i = 1 To Length(s)
		If Mid(s, i, 1) = "1" Then
			k += "0"
		Else
			k += "1"
		End If
	Next i
	Thue_Morse = s + k
End Function

Print tm
For j = 1 To 7
	tm = Thue_Morse(tm)
	Print tm
Next j
End

Output:

Igual que la entrada de FreeBASIC.

Sinclair ZX81 BASIC

 10 LET T$="0"
 20 PRINT "T0=";T$
 30 FOR I=1 TO 7
 40 PRINT "T";I;"=";
 50 FOR J=1 TO LEN T$
 60 IF T$(J)="0" THEN GOTO 90
 70 LET T$=T$+"0"
 80 GOTO 100
 90 LET T$=T$+"1"
100 NEXT J
110 PRINT T$
120 NEXT I

Output:

T0=0
T1=01
T2=0110
T3=01101001
T4=0110100110010110
T5=01101001100101101001011001101001
T6=0110100110010110100101100110100110010110011010010110100110010110
T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

BBC BASIC

REM >thuemorse
tm$ = "0"
PRINT tm$
FOR i% = 1 TO 8
  tm$ = FN_thue_morse(tm$)
  PRINT tm$
NEXT
END
:
DEF FN_thue_morse(previous$)
LOCAL i%, tm$
tm$ = ""
FOR i% = 1 TO LEN previous$
  IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"
NEXT
= previous$ + tm$

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

BCPL

get "libhdr"

let parity(x) = 
    x=0 -> 0,
    (x&1) neqv parity(x>>1)
    
let start() be
$(  for i=0 to 63 do writen(parity(i))
    wrch('*N')
$)

Output:

0110100110010110100101100110100110010110011010010110100110010110

Befunge

Translation of: C

This implements the algorithm that counts the 1 bits in the binary representation of the sequence number.

:0\:!v!:\+g20\<>*:*-!#@_
86%2$_:2%02p2/^^82:+1,+*

Output:

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

Binary Lambda Calculus

The (infinite) Thue-Morse sequence is output by the 115 bit BLC program

0001000110100001010100011010000000000101101110000101100000010111111101011001111001111110111110000011001011010000010

as documented in https://github.com/tromp/AIT/blob/master/characteristic_sequences/thue-morse.lam

Output:

01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101100110100110010110100101100110100101101001...

BQN

TM ← {𝕩↑(⊢∾¬)⍟(1+⌈2⋆⁼𝕩)⥊0}

TM 25 #get first 25 elements

Output:

⟨ 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 ⟩

C

C: Using string operations

Translation of: Java

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]){
	char sequence[256+1] = "0";
	char inverse[256+1] = "1";
	char buffer[256+1];
	int i;
	
	for(i = 0; i < 8; i++){
		strcpy(buffer, sequence);
		strcat(sequence, inverse);
		strcat(inverse, buffer);
	}
	
	puts(sequence);
	return 0;
}

Output:

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

C: By counting ones in binary representation of an iterator

#include <stdio.h>

/**
 * description : Counts the number of bits set to 1
 *        input: the number to have its bit counted
 *       output: the number of bits set to 1
 */
unsigned count_bits(unsigned v) {
    unsigned c = 0;
    while (v) {
        c += v & 1;
        v >>= 1;
    }

    return c;
}

int main(void) {
    for (unsigned i = 0; i < 256; ++i) {
        putchar('0' + count_bits(i) % 2);
    }
    putchar('\n');

    return 0;
}

Output:

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

C: By counting ones in binary representation of an iterator (w/User options)

 #include <stdio.h>

/**
 * description : Counts the number of bits set to 1
 *        input: the number to have its bit counted
 *       output: the number of bits set to 1
 */
unsigned count_bits(unsigned v) {
    unsigned c = 0;
    while (v) {
        c += v & 1;
        v >>= 1;
    }

    return c;
}

int main(void) {
    /*          i: loop iterator
     *     length: the length of the sequence to be printed
     * ascii_base: the lower char for use when printing
     */
    unsigned i, length = 0;
    int ascii_base;


    /* scan in sequence length */
    printf("Sequence length: ");
    do {
        scanf("%u", &length);
    } while (length == 0);


    /* scan in sequence mode */
    printf("(a)lpha or (b)inary: ");
    do {
        ascii_base = getchar();
    } while ((ascii_base != 'a') && (ascii_base != 'b'));
    ascii_base = ascii_base == 'b' ? '0' : 'A';


    /* print the Thue-Morse sequence */
    for (i = 0; i < length; ++i) {
        putchar(ascii_base + count_bits(i) % 2);
    }
    putchar('\n');

    return 0;
}

Output:

Sequence length: 256
(a)lpha or (b)inary: b
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

C#

Translation of: Java

using System;
using System.Text;

namespace ThueMorse
{
    class Program
    {
        static void Main(string[] args)
        {
            Sequence(6);
        }

        public static void Sequence(int steps)
        {
            var sb1 = new StringBuilder("0");
            var sb2 = new StringBuilder("1");
            for (int i = 0; i < steps; i++)
            {
                var tmp = sb1.ToString();
                sb1.Append(sb2);
                sb2.Append(tmp);
            }
            Console.WriteLine(sb1);
            Console.ReadLine();
        }
    }
}

0110100110010110100101100110100110010110011010010110100110010110

C++

#include <iostream>
#include <iterator>
#include <vector>
int main( int argc, char* argv[] ) {
    std::vector<bool> t;
    t.push_back( 0 );
    size_t len = 1;
    std::cout << t[0] << "\n";
    do {
        for( size_t x = 0; x < len; x++ )
            t.push_back( t[x] ? 0 : 1 );
        std::copy( t.begin(), t.end(), std::ostream_iterator<bool>( std::cout ) );
        std::cout << "\n";
        len = t.size();
    } while( len < 60 );
    return 0;
}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

CLU

% Yields an infinite Thue-Morse sequence, digit by digit
tm = iter () yields (char)
    n: int := 1
    s: string := "0"
    while true do
        while n <= string$size(s) do
            yield(s[n])
            n := n + 1
        end
        s2: array[char] := array[char]$[]
        for c: char in string$chars(s) do
            if c='0' 
                then array[char]$addh(s2, '1')
                else array[char]$addh(s2, '0')
            end
        end
        s := s || string$ac2s(s2)
    end
end tm

% Print the first 64 characters
start_up = proc ()
    AMOUNT = 64
    po: stream := stream$primary_output()
    n: int := 0
    for c: char in tm() do
        stream$putc(po, c)
        n := n + 1
        if n = AMOUNT then break end
    end
end start_up

Output:

0110100110010110100101100110100110010110011010010110100110010110

COBOL

       IDENTIFICATION DIVISION.
       PROGRAM-ID. THUE-MORSE.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 STRINGS.
          03 CURRENT-STATE      PIC X(64).
          03 TEMP               PIC X(64).

       PROCEDURE DIVISION.
       BEGIN.
           MOVE "0" TO CURRENT-STATE.
           PERFORM THUE-MORSE-STEP 8 TIMES.
           DISPLAY CURRENT-STATE.
           STOP RUN.

       THUE-MORSE-STEP.
           MOVE CURRENT-STATE TO TEMP.
           INSPECT TEMP REPLACING ALL '0' BY 'X'.
           INSPECT TEMP REPLACING ALL '1' BY '0'.
           INSPECT TEMP REPLACING ALL 'X' BY '1'.
           STRING CURRENT-STATE DELIMITED BY SPACE,
                  TEMP DELIMITED BY SPACE
                  INTO CURRENT-STATE.

Output:

0110100110010110100101100110100110010110011010010110100110010110

Common Lisp

(defun bit-complement (bit-vector)
  (loop with result = (make-array (length bit-vector) :element-type 'bit)
        for b across bit-vector
        for i from 0
        do (setf (aref result i) (- 1 b))
        finally (return result)))

(defun next (bit-vector)
  (concatenate 'bit-vector bit-vector (bit-complement bit-vector)))

(defun print-bit-vector (bit-vector)
  (loop for b across bit-vector
        do (princ b)
        finally (terpri)))

(defun thue-morse (max)
  (loop repeat (1+ max)
        for value = #*0 then (next value)
        do (print-bit-vector value)))

(thue-morse 6)

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Cowgol

include "cowgol.coh";

# Find the N'th digit in the Thue-Morse sequence
sub tm(n: uint32): (d: uint8) is
    var n2 := n;
    while n2 != 0 loop
        n2 := n2 >> 1;
        n := n ^ n2;
    end loop;
    d := (n & 1) as uint8;
end sub;

# Print the first 64 digits
var i: uint32 := 0;
while i < 64 loop
    print_char('0' + tm(i));
    i := i + 1;
end loop;
print_nl();

Output:

0110100110010110100101100110100110010110011010010110100110010110

Crystal

Translation of: Javascript

steps = 6

tmp = ""
s1 = "0"
s2 = "1"

steps.times {
  tmp = s1
  s1 += s2
  s2 += tmp
}

puts s1

Output:

0110100110010110100101100110100110010110011010010110100110010110

D

Translation of: C

import std.range;
import std.stdio;

struct TM {
    private char[] sequence = ['0'];
    private char[] inverse = ['1'];
    private char[] buffer;

    enum empty = false;
    
    auto front() {
        return sequence;
    }
    
    auto popFront() {
        buffer = sequence;
        sequence ~= inverse;
        inverse ~= buffer;
    }
}

void main() {
    TM sequence;

    foreach (step; sequence.take(8)) {
        writeln(step);
    }
}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Delphi

See Pascal.

Draco

/* Find the N'th digit in the Thue-Morse sequence */
proc nonrec tm(word n) byte:
    word n2;
    n2 := n;
    while n2 ~= 0 do
        n2 := n2 >> 1;
        n := n >< n2
    od;
    n & 1
corp

/* Print the first 64 digits */
proc nonrec main() void:
    byte i;
    for i from 0 upto 63 do
        write(tm(i):1)
    od
corp

Output:

0110100110010110100101100110100110010110011010010110100110010110

DuckDB

Works with: DuckDB version V1.0

If run using DuckDB, the program at #SQL hangs unless a termination criterion is specified. With `LIMIT 1 OFFSET 4` to force termination, DuckDB produces the following table:

┌──────────┐
│    a     │
│ varchar  │
├──────────┤
│ 01101001 │
└──────────┘

t(n)

We shall adapt the program at #SQL to define a DuckDB function that produces t(n), the n-th term of the Thue-Morse sequence (starting at n=1), as follows:

create or replace function t(n) as (
  with recursive mx as (select (ceil(log(n) / log(2))) as mx),
  cte as (
    select '0' as a,
            0 as ix
    union all
    select replace(replace(hex(a),'30','01'),'31','10') as a,
           ix+1 as ix
    from cte, mx
    where ix < mx
  )
  select last(a[n] order by ix) from cte 
);

## Example:
select t(1),  t(2),  t(3), t(4), t(5), t(100);

Output:

┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│  t(1)   │  t(2)   │  t(3)   │  t(4)   │  t(5)   │ t(100)  │
│ varchar │ varchar │ varchar │ varchar │ varchar │ varchar │
├─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ 0       │ 1       │ 1       │ 0       │ 1       │ 0       │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

TM(n)

We can similarly use a simpler and more efficient CTE to define a function that produces a character string consisting of the first n terms in the Thue-Morse sequence:

create or replace function TM(n) as (
create or replace function TM(n) as (
  with recursive mx as (select (ceil(log(n) / log(2))) as mx),
  cte as (
    select '0' as sb0, '1' as sb1, 0 as ix
    union all
    select (sb0 || sb1) as sb0,
           (sb1 || sb0) as sb1,
           ix+1,
           from cte, mx
           where ix < mx
  )
  select last(sb0[:n] order by ix) from cte 
);
## Example:
select TM(100);

Output:

┌──────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                               tm(100)                                                │
│                                               varchar                                                │
├──────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110 │
└──────────────────────────────────────────────────────────────────────────────────────────────────────┘

EasyLang

Translation of: BASIC256

func$ tmorse s$ .
   for i to len s$
      if substr s$ i 1 = "1"
         k$ &= "0"
      else
         k$ &= "1"
      .
   .
   return s$ & k$
.
tm$ = "0"
print tm$
for j to 7
   tm$ = tmorse tm$
   print tm$
.

Elena

Translation of: C#

ELENA 6.x :

import extensions;
import system'text;

sequence(int steps)
{
    var sb1 := TextBuilder.load("0");
    var sb2 := TextBuilder.load("1"); 
    for(int i := 0; i < steps; i += 1)
    {
        var tmp := sb1.Value;
        sb1.write(sb2);
        sb2.write(tmp)
    };
    console.printLine(sb1).readLine()
}
 
public program()
{
    sequence(6)
}

Output:

0110100110010110100101100110100110010110011010010110100110010110

Elixir

Enum.reduce(0..6, '0', fn _,s ->
  IO.puts s
  s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end)
end)

# or
Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end)
|> Enum.take(7)
|> Enum.each(&IO.puts/1)

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Excel

LAMBDA

Binding the name thueMorse to the following lambda expression in the Name Manager of the Excel WorkBook:

(See LAMBDA: The ultimate Excel worksheet function)

Works with: Office 365 betas 2021

thueMorse
=LAMBDA(n,
    APPLYN(n)(
        LAMBDA(bits,
            APPENDCOLS(bits)(
                LAMBDA(x,
                    IF(0 < x, 0, 1)
                )(bits)
            )
        )
    )(0)
)

and also assuming the following generic bindings in the Name Manager for the WorkBook:

APPLYN
=LAMBDA(n,
    LAMBDA(f,
        LAMBDA(x,
            IF(0 < n,
                APPLYN(n - 1)(f)(
                    f(x)
                ),
                x
            )
        )
    )
)


APPENDCOLS
=LAMBDA(xs,
    LAMBDA(ys,
        LET(
            nx, COLUMNS(xs),
            colIndexes, SEQUENCE(1, nx + COLUMNS(ys)),
            rowIndexes, SEQUENCE(MAX(ROWS(xs), ROWS(ys))),

            IFERROR(
                IF(nx < colIndexes,
                    INDEX(ys, rowIndexes, colIndexes - nx),
                    INDEX(xs, rowIndexes, colIndexes)
                ),
                NA()
            )
        )
    )
)

Output:

The formula in cell B2 below defines the array of 2^5 = 32 bits which populates the range B2:AG2

	fx	=thueMorse(A2)
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	AA	AB	AC	AD	AE	AF	AG
1	Iterations
2	5	0	1	1	0	1	0	0	1	1	0	0	1	0	1	1	0	1	0	0	1	0	1	1	0	0	1	1	0	1	0	0	1

Or, as a string, showing up to 2^6 = 64 bits:

	fx	=CONCAT(VALUETOTEXT(thueMorse(A2)))
	A	B
1	Iterations	Thue-Morse sequence
2	0	0
3	1	01
4	2	0110
5	3	01101001
6	4	0110100110010110
7	5	01101001100101101001011001101001
8	6	0110100110010110100101100110100110010110011010010110100110010110

F#

// Thue-Morse. Nigel Galloway: April 16th., 2024
let rec fG n g=match n with 0->g |1->g+1 |n ->fG(n/2)(g+n&&&1)
let thueMorse=Seq.initInfinite(fun n->(fG n 0)%2)
thueMorse|>Seq.take 25|>Seq.iter(printf "%d "); printfn ""

Output:

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0

Factor

Works with: Factor version 0.98

USING: io kernel math math.parser sequences ;

: thue-morse ( seq n -- seq' )
    [ [ ] [ [ 1 bitxor ] map ] bi append ] times ;
    
: print-tm ( seq -- ) [ number>string ] map "" join print ;

7 <iota> [ { 0 } swap thue-morse print-tm ] each

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Fortran

Works with: Fortran version 90 and later

program thue_morse
  implicit none
  logical :: f(32) = .false.
  integer :: n = 1

  do
    write(*,*) f(1:n)
    if (n > size(f)/2) exit  
    f(n+1:2*n) = .not. f(1:n)
    n = n * 2
  end do
  
end program thue_morse

Output:

  F
  F  T
  F  T  T  F
  F  T  T  F  T  F  F  T
  F  T  T  F  T  F  F  T  T  F  F  T  F  T  T  F
  F  T  T  F  T  F  F  T  T  F  F  T  F  T  T  F  T  F  F  T  F  T  T  F  F  T  T  F  T  F  F  T

FreeBASIC

Dim As String tm = "0"

Function Thue_Morse(s As String) As String
    Dim As String k = ""
    For i As Integer = 1 To Len(s)
        If Mid(s, i, 1) = "1" Then 
            k += "0" 
        Else 
            k += "1"
        End If
    Next i
    Thue_Morse = s + k
End Function

Print tm
For j As Integer = 1 To 7
    tm = Thue_Morse(tm)
    Print tm
Next j
End

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

FutureBasic

local fn ThueMorse( s as Str255 ) as Str255
  Str255 k
  short  i
  
  k = ""
  for i = 1 to len$(s)
    if mid$(s, i, 1) == "1"
      k += "0"
    else
      k += "1"
    end if
  next
end fn = s + k

local fn DoIt
  Str255 tm
  short  i
  
  tm = "0"
  print tm
  for i = 1 to 7
    tm = fn ThueMorse( tm )
    print tm
  next
end fn

fn DoIt

HandleEvents

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website.

In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

Solution 1

Solution 2

Solution 3

Solution 4

Notice that this solution generates a string.

Solution 5

Notice that this solution generates a string.

Solution 6

Notice that this solution generates a string.

Solution 7. L-system

There are generic functions written in Fōrmulæ to compute an L-system in the page L-system.

The program that creates a Thue-Morse sequence is:

Go

// prints the first few members of the Thue-Morse sequence

package main

import (
    "fmt"
    "bytes"
)

// sets tmBuffer to the next member of the Thue-Morse sequence
// tmBuffer must contain a valid Thue-Morse sequence member before the call
func nextTMSequenceMember( tmBuffer * bytes.Buffer ) {
    // "flip" the bytes, adding them to the buffer
    for b, currLength, currBytes := 0, tmBuffer.Len(), tmBuffer.Bytes() ; b < currLength; b ++ {
        if currBytes[ b ] == '1' {
            tmBuffer.WriteByte( '0' )
        } else {
            tmBuffer.WriteByte( '1' )
        }
    }
}
    
func main() {
    var tmBuffer bytes.Buffer
    // initial sequence member is "0"
    tmBuffer.WriteByte( '0' )
    fmt.Println( tmBuffer.String() )
    for i := 2; i <= 7; i ++ {
        nextTMSequenceMember( & tmBuffer )
        fmt.Println( tmBuffer.String() )
    }
}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Haskell

Computing progressively longer prefixes of the sequence:

thueMorsePxs :: [[Int]]
thueMorsePxs = iterate ((++) <*> map (1 -)) [0]

{-
    = Control.Monad.ap (++) (map (1-)) `iterate` [0]
    = iterate (\ xs -> (++) xs (map (1-) xs)) [0]
    = iterate (\ xs -> xs ++ map (1-) xs) [0]
-}
main :: IO ()
main = print $ thueMorsePxs !! 5

Output:

[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]

The infinite sequence itself:

thueMorse :: [Int]
thueMorse = 0 : g 1
  where
    g i = (1 -) <$> take i thueMorse <> g (2 * i)
 
main :: IO ()
main = print $ take 33 thueMorse

Output:

[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1]

J

We only show a prefix of the sequence:

   (, -.)@]^:[&0]9
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...

Or, more compactly:

   ' '-.~":(, -.)@]^:[&0]9
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...

Java

public class ThueMorse {

    public static void main(String[] args) {
        sequence(6);
    }

    public static void sequence(int steps) {
        StringBuilder sb1 = new StringBuilder("0");
        StringBuilder sb2 = new StringBuilder("1");
        for (int i = 0; i < steps; i++) {
            String tmp = sb1.toString();
            sb1.append(sb2);
            sb2.append(tmp);
        }
        System.out.println(sb1);
    }
}

0110100110010110100101100110100110010110011010010110100110010110

JavaScript

ES5

Translation of: Java

(function(steps) {
    'use strict';
    var i, tmp, s1 = '0', s2 = '1';
    for (i = 0; i < steps; i++) {
        tmp = s1;
        s1 += s2;
        s2 += tmp;
    }
    console.log(s1);    
})(6);

0110100110010110100101100110100110010110011010010110100110010110

ES6

(() => {
    'use strict';

    // thueMorsePrefixes :: () -> [[Int]]
    const thueMorsePrefixes = () =>
        iterate(
            ap(append)(
                map(x => 1 - x)
            )
        )([0]);

    // ----------------------- TEST -----------------------
    const main = () =>
        // Fifth iteration.
        // 2 ^ 5 = 32 terms of the Thue-Morse sequence.
        showList(
            index(thueMorsePrefixes())(
                5
            )
        );


    // ---------------- GENERIC FUNCTIONS -----------------

    // ap :: (a -> b -> c) -> (a -> b) -> a -> c
    const ap = f =>
        // Applicative instance for functions.
        // f(x) applied to g(x).
        g => x => f(x)(
            g(x)
        );


    // append (++) :: [a] -> [a] -> [a]
    // append (++) :: String -> String -> String
    const append = xs =>
        // A list or string composed by
        // the concatenation of two others.
        ys => xs.concat(ys);


    // index (!!) :: Generator (Int, a) -> Int -> Maybe a
    const index = xs =>
        i => (take(i)(xs), xs.next().value);


    // iterate :: (a -> a) -> a -> Gen [a]
    const iterate = f =>
        function*(x) {
            let v = x;
            while (true) {
                yield(v);
                v = f(v);
            }
        };


    // map :: (a -> b) -> [a] -> [b]
    const map = f =>
        // The list obtained by applying f
        // to each element of xs.
        // (The image of xs under f).
        xs => xs.map(f);


    // showList :: [a] -> String
    const showList = xs =>
        '[' + xs.map(x => x.toString())
        .join(',')
        .replace(/[\"]/g, '') + ']';


    // take :: Int -> [a] -> [a]
    // take :: Int -> String -> String
    const take = n =>
        // The first n elements of a list,
        // string of characters, or stream.
        xs => 'GeneratorFunction' !== xs
        .constructor.constructor.name ? (
            xs.slice(0, n)
        ) : [].concat.apply([], Array.from({
            length: n
        }, () => {
            const x = xs.next();
            return x.done ? [] : [x.value];
        }));

    // MAIN ---
    return main();
})();

Output:

[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]

jq

Works with: jq

Works with gojq, the Go implementation of jq

`thueMorse` as defined here generates an indefinitely long stream of the Thue-Morse integers:

def thueMorse:
  0,
  ({sb0: "0", sb1: "1", n:1 }
   | while( true;
      {n: (.sb0|length),
       sb0: (.sb0 + .sb1),
       sb1: (.sb1 + .sb0)} )
   | .sb0[.n:]
   | explode[]
   | . - 48);

Example:

[limit(100;thueMorse)] | join("")

Output:

 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110

Julia

Works with: Julia version 0.6

function thuemorse(len::Int)
    rst = Vector{Int8}(len)
    rst[1] = 0
    i, imax = 2, 1
    while i ≤ len
        while i ≤ len && i ≤ 2 * imax
            rst[i] = 1 - rst[i-imax]
            i += 1
        end
        imax *= 2
    end
    return rst
end

println(join(thuemorse(100)))

Output:

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110

Kotlin

Kotlin: From java

Translation of: Java

The original Java code, as translated to Kotlin, with a few cleanups.

fun thueMorse(n: Int): String {
    val sb0 = StringBuilder("0")
    val sb1 = StringBuilder("1")
    repeat(n) {
        val tmp = sb0.toString()
        sb0.append(sb1)
        sb1.append(tmp)
    }
    return sb0.toString()
}

fun main() {
    for (i in 0..6) println("$i : ${thueMorse(i)}")
}

Output:

0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110

Kotlin: Alternative

Same general idea as above, but using a few Kotlin specific code shortcuts.

fun thueMorse(n: Int): String {
    val pair = "0" to "1"
    repeat(n) { pair = with(pair) { first + second to second + first } }
    return pair.first
}

fun main() {
    for (i in 0..6) println("$i : ${thueMorse(i)}")
}

Output:

0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110

Lambdatalk

{def thue_morse
 {def thue_morse.r
  {lambda {:steps :s1 :s2 :i}
   {if {> :i :steps}
    then :s1
    else {thue_morse.r :steps :s1:s2 :s2:s1 {+ :i 1}}}}}
 {lambda {:steps}
  {thue_morse.r :steps 0 1 1}}}
-> thue_morse

{thue_morse 6}
-> 0110100110010110100101100110100110010110011010010110100110010110

Lua

ThueMorse = {sequence = "0"}

function ThueMorse:show ()
    print(self.sequence)
end

function ThueMorse:addBlock ()
    local newBlock = ""
    for bit = 1, self.sequence:len() do
        if self.sequence:sub(bit, bit) == "1" then
            newBlock = newBlock .. "0"
        else
            newBlock = newBlock .. "1"
        end
    end
    self.sequence = self.sequence .. newBlock
end

for i = 1, 5 do
    ThueMorse:show()
    ThueMorse:addBlock()
end

Output:

0
01
0110
01101001
0110100110010110

M2000 Interpreter

Adapted from Java.

thuemorse$=lambda$ (n as integer)->{
		def sb0$="0", sb1$="1"
		n=max.data(0, n)
		=lambda$
			sb0$, sb1$,
			n, park$
			(many)->{
			if n<0 and park$="" then exit
			while n>0
				tmp$=sb0$
				sb0$+=sb1$
				sb1$+=tmp$
				n--
			end while
			if n>=0 then n-- :park$+=sb0$
			if many<len(park$) then
				=left$(park$, many)
				park$=mid$(park$, many+1)
			else
				=park$:park$=""
			end if
			 
		}
}
document log$
For i=0 to 7
	Print "T"+(i+1)+":";
	t$=thuemorse$(i)
	do
		batch$=t$(16)
		if batch$<>"" then
			Print batch$;   ' here we can do anything for each batch$
		else
			Print
			exit
		end if
	always
next i

MODULE FromZX81_BASIC {
// T$(J) -> mid$(T$, J, 1)
// THEN GOTO 90  (is ok but here we use THEN 90) 
	 10 LET T$="0"
	 20 PRINT "T0=";T$
	 30 FOR I=1 TO 7
	 40 PRINT "T";I;"=";
	 50 FOR J=1 TO LEN(T$)
	 60 IF MID$(T$,J, 1)="0" THEN 90
	 70 LET T$=T$+"0"
	 80 GOTO 100
	 90 LET T$=T$+"1"
	100 NEXT J
	110 PRINT T$
	120 NEXT I
}
FromZX81_BASIC
Module Modern {
	NextMorse=lambda t="0", s="", i=1 -> {
			t+=replace$("b", "1", replace$("1", "0", replace$("0", "b", s)))
			="T"+i+"="+t
			i++ : s=t
	}
	for i=1 to 8
		? NextMorse()
	next
}
modern

Output:

3 times:

T0=0
T1=01
T2=0110
T3=01101001
T4=0110100110010110
T5=01101001100101101001011001101001
T6=0110100110010110100101100110100110010110011010010110100110010110
T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

MACRO-11

        .TITLE  THUE
        .MCALL  .TTYOUT,.EXIT
THUE::  MOV     #100,R3         ; 64 ITEMS
        CLR     R2
1$:     JSR     PC,SEQ          ; GET THUE-MORSE SEQUENCE ITEM
        ADD     #60,R0          ; MAKE ASCII
        .TTYOUT                 ; PRINT
        INC     R2
        SOB     R3,1$
        .EXIT

        ; LET R0 = R2'TH ITEM IN THUE MORSE SEQUENCE
SEQ:    CLR     R0
        MOV     #20,R1
1$:     ROR     R0
        XOR     R2,R0
        SOB     R1,1$
        BIC     #^C1,R0
        RTS     PC
        .END    THUE

Output:

0110100110010110100101100110100110010110011010010110100110010110

Mathematica /Wolfram Language

ThueMorse[Range[20]]

Output:

{1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0}

MATLAB

MATLAB: By counting set ones in binary representation

tmSequence = thue_morse_digits(20);
disp(tmSequence);

function tmSequence = thue_morse_digits(n)
    tmSequence = zeros(1, n);
    for i = 0:(n-1)
        binStr = dec2bin(i);
        numOnes = sum(binStr == '1');
        tmSequence(i+1) = mod(numOnes, 2);
    end
end

Output:

     0     1     1     0     1     0     0     1     1     0     0     1     0     1     1     0     1     0     0     1

Miranda

main :: [sys_message]
main = [Stdout (show (take 30 thue) ++ "\n")]

thue :: [num]
thue = 0 : 1 : concat [[x, 1-x] | x<-tl thue]

Output:

[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]

Modula-2

MODULE ThueMorse;
FROM Strings IMPORT Concat;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

PROCEDURE Sequence(steps : CARDINAL);
TYPE String = ARRAY[0..128] OF CHAR;
VAR sb1,sb2,tmp : String;
    i : CARDINAL;
BEGIN
    sb1 := "0";
    sb2 := "1";

    WHILE i<steps DO
        tmp := sb1;
        Concat(sb1, sb2, sb1);
        Concat(sb2, tmp, sb2);
        INC(i);
    END;
    WriteString(sb1);
    WriteLn;
END Sequence;

BEGIN
    Sequence(6);
    ReadChar;
END ThueMorse.

NewLISP

(define (Thue-Morse loops)
    (setf TM '(0))
    (println TM)
    (for (i 1 (-- loops))
        (setf tmp TM)
        (replace '0 tmp '_)
        (replace '1 tmp '0)
        (replace '_ tmp '1)
        (setf TM (append TM tmp))
        (println TM)
    )
)

(Thue-Morse 5)
(exit)

Output:

(0)
(0 1)
(0 1 1 0)
(0 1 1 0 1 0 0 1)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0)

Nim

Using an iterator and sequences concatenations

import sequtils, strutils

iterator thueMorse(maxSteps = int.high): string =
  var val = @[0]
  var count = 0
  while true:
    yield val.join()
    inc count
    if count == maxSteps: break
    val &= val.mapIt(1 - it)

for bits in thueMorse(6):
  echo bits

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001

Using fast sequence generation algorithm from Wikipedia

type Bit = 0..1

proc thueMorse(seqLength: Positive): string =
  var val = Bit(0)
  for n in 0..<seqLength:
    let x = n xor (n - 1)
    if ((x xor x shr 1) and 0x55555555) != 0:
      val = 1 - val
    result.add chr(val + ord('0'))

echo thueMorse(64)

Output:

0110100110010110100101100110100110010110011010010110100110010110

OASYS Assembler

; Thue-Morse sequence

[*'A]               ; Ensure the vocabulary is not empty
[&]                 ; Declare the initialization procedure
%#1>                ; Initialize length counter
%@*>                ; Create first object
,#1>                ; Initialize loop counter
:                   ; Begin loop
  %@<.#<PI          ; Print current cell
  *.#%@<.#<NOT>     ; Create new cell
  %@%@<NXT>         ; Advance to next cell
  ,#,#<DN>          ; Decrement loop counter
  ,#</              ; Check if loop counter is now zero
    %#%#<2MUL>      ; Double length counter
    ,#%#<>          ; Reset loop counter
    %@FO>           ; Reset object pointer
    CR              ; Line break
|                   ; Repeat loop

The standard DOS-based interpreter will display an error message about word too long after 7 lines are output; this is because the 8th line does not fit in 80 columns.

Objeck

Translation of: Java

class ThueMorse {
  function : Main(args : String[]) ~ Nil {
    Sequence(6);
  }

  function : Sequence(steps : Int) ~ Nil {
    sb1 := "0";
    sb2 := "1";
    for(i := 0; i < steps; i++;) {
      tmp := String->New(sb1);
      sb1 += sb2;
      sb2 += tmp;
    };
    sb1->PrintLine();
  }
}

Output:

0110100110010110100101100110100110010110011010010110100110010110

OCaml

By counting ones in binary representation of an iterator

Translation of: C

(* description: Counts the number of bits set to 1
         input: the number to have its bit counted
        output: the number of bits set to 1 *)
let count_bits v =
  let rec aux c v =
    if v <= 0 then c
    else aux (c + (v land 1)) (v lsr 1)
  in
  aux 0 v

let () =
  for i = 0 to pred 256 do
    print_char (
      match (count_bits i) mod 2 with
      | 0 -> '0'
      | 1 -> '1'
      | _ -> assert false)
  done;
  print_newline ()

Using string operations

Translation of: Objeck

let sequence steps =
  let sb1 = Buffer.create 100 in
  let sb2 = Buffer.create 100 in
  Buffer.add_char sb1 '0';
  Buffer.add_char sb2 '1';
  for i = 0 to pred steps do
    let tmp = Buffer.contents sb1 in
    Buffer.add_string sb1 (Buffer.contents sb2);
    Buffer.add_string sb2 tmp;
  done;
  (Buffer.contents sb1)

let () =
  print_endline (sequence 6);

Pascal

Works with: Free Pascal

Works with: Delphi

Like the C++ Version [[1]] the lenght of the sequence is given in advance.

Program ThueMorse;
 
function fThueMorse(maxLen: NativeInt):AnsiString;
//double by appending the flipped original 0 -> 1;1 -> 0
//Flipping between two values:x oszillating A,B,A,B -> x_next = A+B-x
//Beware A+B < High(Char), the compiler will complain ...
const
  cVal0 = '^';cVal1 = 'v';//  cVal0 = '0';cVal1 = '1';
 
var
  pOrg,
  pRpl : pansiChar;
  i,k,ml : NativeUInt;//MaxLen: NativeInt
Begin
  iF maxlen < 1 then
  Begin
    result := '';
    EXIT;
  end;
  //setlength only one time
  setlength(result,Maxlen);
 
  pOrg := @result[1];
  pOrg[0] := cVal0;
  IF maxlen = 1 then
    EXIT;
 
  pRpl := pOrg;
  inc(pRpl);
  k := 1;
  ml:= Maxlen;
  repeat
    i := 0;
    repeat
      pRpl[0] := ansichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
      inc(pRpl);
      inc(i);
    until i>=k;
    inc(k,k);
  until k+k> ml;
  // the rest
  i := 0;
  k := ml-k;
  IF k > 0 then
    repeat
      pRpl[0] := ansichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
      inc(pRpl);
      inc(i)
    until i>=k;
end;

var
 i : integer;
Begin
  For i := 0 to 8 do
    writeln(i:3,'  ',fThueMorse(i));
  fThueMorse(1 shl 30);
  {$IFNDEF LINUX}readln;{$ENDIF}
end.

Output:

Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi
without -O4 -> 2 secs

 0
 1  ^
 2  ^v
 3  ^vv
 4  ^vv^
 5  ^vv^v
 6  ^vv^v^
 7  ^vv^v^^
 8  ^vv^v^^v

not written: 1 shl 30 == 1GB

real  0m0.806s user  0m0.563s sys 0m0.242s

Perl

Works with: Perl version 5.x

sub complement
{
    my $s = shift;

    $s =~ tr/01/10/;

    return $s;
}

my $str = '0';

for (0..6) {
    say $str;
    $str .= complement($str);
}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Phix

string tm = "0"
for i=1 to 8 do
    printf(1,"%s\n",tm)
    tm &= sq_sub('0'+'1',tm)
end for

Output:

"0"
"01"
"0110"
"01101001"
"0110100110010110"
"01101001100101101001011001101001"
"0110100110010110100101100110100110010110011010010110100110010110"
"01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001"

Phixmonti

def inverte
	dup len	
	for
		var i
		i get not i set
	endfor
enddef

0 1 tolist
8 for
    .
    dup print nl nl
    inverte chain
endfor

PHP

Fast sequence generation - This implements the algorithm that find the highest-order bit in the binary representation of n that is different from the same bit in the representation of n − 1 (see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence)

<?php

function thueMorseSequence($length) {
    $sequence = '';
    for ($digit = $n = 0 ; $n < $length ; $n++) {
        $x = $n ^ ($n - 1);
        if (($x ^ ($x >> 1)) & 0x55555555) {
            $digit = 1 - $digit;
        }
        $sequence .= $digit;
    }
    return $sequence;
}

for ($n = 10 ; $n <= 100 ; $n += 10) {
    echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL;
}

Output:

 10 : 0110100110
 20 : 01101001100101101001
 30 : 011010011001011010010110011010
 40 : 0110100110010110100101100110100110010110
 50 : 01101001100101101001011001101001100101100110100101
 60 : 011010011001011010010110011010011001011001101001011010011001
 70 : 0110100110010110100101100110100110010110011010010110100110010110100101
 80 : 01101001100101101001011001101001100101100110100101101001100101101001011001101001
 90 : 011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110
100 : 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110

PicoLisp

(let R 0
   (prinl R)
   (for (X 1 (>= 32 X))
      (setq R
         (bin
            (pack
               (bin R)
               (bin (x| (dec (** 2 X)) R)) ) ) )
      (prinl (pack 0 (bin R)))
      (inc 'X X) ) )

PL/M

100H:
BDOS: PROCEDURE (F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PUT$CHAR: PROCEDURE (C); DECLARE C BYTE; CALL BDOS(2,C); END PUT$CHAR;

/* FIND THE NTH ELEMENT OF THE THUE-MORSE SEQUENCE */
THUE: PROCEDURE (N) BYTE;
    DECLARE N ADDRESS;
    N = N XOR SHR(N,8);
    N = N XOR SHR(N,4);
    N = N XOR SHR(N,2);
    N = N XOR SHR(N,1);
    RETURN N AND 1;
END THUE;

/* PRINT THE FIRST 64 ELEMENTS */
DECLARE I BYTE;
DO I=0 TO 63;
    CALL PUT$CHAR('0' + THUE(I));
END;

CALL EXIT;
EOF

Output:

0110100110010110100101100110100110010110011010010110100110010110

PowerShell

function New-ThueMorse ( $Digits )
    {
    #  Start with seed 0
    $ThueMorse = "0"
 
    #  Decrement digits remaining
    $Digits--
 
    #  While we still have digits to calculate...
    While ( $Digits -gt 0 )
        {
        #  Number of digits we'll get this loop (what we still need up to the maximum available), corrected to 0 base
        $LastDigit = [math]::Min( $ThueMorse.Length, $Digits ) - 1
 
        #  Loop through each digit
        ForEach ( $i in 0..$LastDigit )
            {
            #  Append the twos complement
            $ThueMorse += ( 1 - $ThueMorse.Substring( $i, 1 ) )
            }
 
        #  Calculate the number of digits still remaining
        $Digits = $Digits - $LastDigit - 1
        }
 
    return $ThueMorse
    }
 
New-ThueMorse 5
New-ThueMorse 16
New-ThueMorse 73

Output:

01101
0110100110010110
0110100110010110100101100110100110010110011010010110100110010110100101100

PureBasic

Translation of: C

EnableExplicit

Procedure.i count_bits(v.i)
  Define c.i
  While v
    c+v&1
    v>>1
  Wend
  ProcedureReturn c
EndProcedure

If OpenConsole()
  Define n.i
  For n=0 To 255      
    Print(Str(count_bits(n)%2))
  Next
  PrintN(~"\n...fin") : Input()
EndIf

Output:

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
...fin

Python

Python: By substitution

m='0'
print(m)
for i in range(0,6):
     m0=m
     m=m.replace('0','a')
     m=m.replace('1','0')
     m=m.replace('a','1')
     m=m0+m
     print(m)

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Python: By counting set ones in binary representation

>>> def thue_morse_digits(digits):
...     return  [bin(n).count('1') % 2 for n in range(digits)]
... 
>>> thue_morse_digits(20)
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

>>>

Python: By substitution system

>>> def thue_morse_subs(chars):
...     ans = '0'
...     while len(ans) < chars:
...         ans = ans.replace('0', '0_').replace('1', '10').replace('_', '1')
...     return ans[:chars]
... 
>>> thue_morse_subs(20)
'01101001100101101001'
>>>

Python: By pair-wise concatenation

>>> def thue_morse(n):
...     (v, i) = ('0', '1')
...     for _ in range(0,n):
...         (v, i) = (v + i, i + v)
...     return v
... 
>>> thue_morse(6)
'0110100110010110100101100110100110010110011010010110100110010110'
>>>

Quackery

This uses the fast sequence generation algorithm from the wiki article.

[ [] 0 rot times
    [ i^ dup 1 - ^
      dup 1 >> ^ hex 55555555 & if
        [ 1 swap - ]
      dup dip
        [ digit join ] ] drop ]     is thue-morse ( n --> $ )

20 thue-morse echo$ cr

Output:

01101001100101101001

R

thue_morse <- function(steps) {
	sb1 <- "0"
	sb2 <- "1"
	for (idx in 1:steps) {
		tmp <- sb1
		sb1 <- paste0(sb1, sb2)
		sb2 <- paste0(sb2, tmp)
	}
	sb1
}
cat(thue_morse(6), "\n")

Output:

0110100110010110100101100110100110010110011010010110100110010110

Racket

#lang racket
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))
(define (thue-morse-step (s "0"))
  (string-append s (list->string (map 1<->0 (string->list s)))))

(define (thue-morse n)
  (let inr ((n (max (sub1 n) 0)) (rv (list "0")))
    (if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))

(for-each displayln (thue-morse 7))

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Raku

(formerly Perl 6)

Works with: rakudo version 2018.03

First 8 of an infinite sequence

.say for (0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *)[^8];

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
^C

Refal

$ENTRY Go {
    = <Prout <ThueMorse 7>>
};

ThueMorse {
    0 e.X = e.X;
    s.N e.X = <ThueMorse <- s.N 1> <ThueMorseStep e.X>>;
};

ThueMorseStep {
    = '0';
    e.X = e.X <Invert e.X>;
};

Invert {
    = ;
    '0' e.X = '1' <Invert e.X>;
    '1' e.X = '0' <Invert e.X>;
};

Output:

0110100110010110100101100110100110010110011010010110100110010110

REXX

using functions

Programming note:   pop count   (or   weight)   is the number of   1's   bits in the binary representation of a number.

/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N .                                    /*obtain the optional argument from CL.*/
if N=='' | N==","  then N= 80                    /*Not specified?  Then use the default.*/
$=                                               /*the Thue─Morse sequence  (so far).   */
         do j=0  to N                            /*generate sequence up to the Nth item.*/
         $= $ || $weight(j) // 2                 /*append the item to the Thue─Morse seq*/
         end   /*j*/
say $
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
$pop:    return  length( space( translate( arg(1), , 0), 0) )     /*count 1's in number.*/
$weight: return  $pop( x2b( d2x( arg(1) ) ) )                     /*dec──►bin, pop count*/

output   when using the default input:

01101001100101101001011001101001100101100110100101101001100101101001011001101001

using in-line code

/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N .                                    /*obtain the optional argument from CL.*/
if N=='' | N==","  then N= 80                    /*Not specified?  Then use the default.*/
$=                                               /*the Thue─Morse sequence  (so far).   */
         do j=0  to N                            /*generate sequence up to the Nth item.*/
         $= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2  /*append to $.*/
         end   /*j*/
say $                                            /*stick a fork in it,  we're all done. */

output   is identical to the 1^st REXX version.

using 2's complement

Programming note:   this method displays the sequence, but it doubles in (binary) length each iteration.

Because of this, the displaying of the output lacks the granularity of the first two REXX versions.

/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N .                                    /*obtain the optional argument from CL.*/
if N=='' | N==","  then N= 6                     /*Not specified?  Then use the default.*/
$= 0                                             /*the Thue─Morse sequence  (so far).   */
         do j=1  for N                           /*generate sequence up to the Nth item.*/
         $= $ || translate($, 10, 01)            /*append $'s  complement to  $  string.*/
         end   /*j*/
say $                                            /*stick a fork in it,  we're all done. */

output   when using the default input:

0110100110010110100101100110100110010110011010010110100110010110

Ring

tm = "0"
see tm 
for n = 1 to 6
    tm = thue_morse(tm)
    see tm
next

func thue_morse(previous)
     tm = ""
     for i = 1 to len(previous)
         if (substr(previous, i, 1) = "1") tm = tm + "0" else tm  = tm + "1" ok
     next
     see nl
     return (previous + tm)

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

RPL

Works with: HP version 48G

We use here the bitwise negation method: it needs few words and is actually faster than the "fast" generation method, because RPL is better in list handling than in bitwise calculations.

≪ { 0 }
   WHILE DUP2 SIZE > REPEAT
      1 OVER - + 
   END
   1 ROT SUB
≫ 'THUEM' STO

20 THUEM

Output:

1: { 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 }

Ruby

puts s = "0"
6.times{puts s << s.tr("01","10")}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Rust

const ITERATIONS: usize = 8;

fn neg(sequence: &String) -> String {
    sequence.chars()
        .map(|ch| {
            (1 - ch.to_digit(2).unwrap()).to_string()
        })
        .collect::<String>()
}

fn main() {
    let mut sequence: String = String::from("0");
    for i in 0..ITERATIONS {
        println!("{}: {}", i + 1, sequence);
        sequence = format!("{}{}", sequence, neg(&sequence));
    }
}

Output:

1: 0
2: 01
3: 0110
4: 01101001
5: 0110100110010110
6: 01101001100101101001011001101001
7: 0110100110010110100101100110100110010110011010010110100110010110
8: 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Scala

def thueMorse(n: Int): String = {
  val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1"))
  (0 until n).foreach { _ =>
    val tmp = sb0.toString()
    sb0.append(sb1)
    sb1.append(tmp)
  }
  sb0.toString()
}

(0 to 6).foreach(i => println(s"$i : ${thueMorse(i)}"))

Output:

See it running in your browser by Scastie (JVM).

Sidef

func recmap(repeat, seed, transform, callback) {
    func (repeat, seed) {
        callback(seed)
        repeat > 0 && __FUNC__(repeat-1, transform(seed))
    }(repeat, seed)
}

recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

SQL

This example is using SQLite.

with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;

You can add a LIMIT clause to the end to limit how many lines of output you want.

Tcl

Since string map correctly handles overlapping replacements, the simple map 0 -> 01; 1 -> 10 can be applied with no special handling:

proc tm_expand {s} {string map {0 01 1 10} $s}
# this could also be written as:
# interp alias {} tm_expand {} string map {0 01 1 10}

proc tm {k} {
    set s 0
    while {[incr k -1] >= 0} {
        set s [tm_expand $s]
    }
    return $s
}

Testing:

for {set i 0} {$i <= 6} {incr i} {
    puts [tm $i]
}

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

For giggles, also note that the above SQL solution can be "natively" applied in Tcl8.5+, which bundles Sqlite as a core extension:

package require sqlite3 ;# available with Tcl8.5+ core
sqlite3 db ""           ;# create in-memory database
set LIMIT 6
db eval {with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select a from a limit $LIMIT} {
    puts $a
}

uBasic/4tH

For x = 0 to 6                         ' sequence loop
  Print Using "_#";x;": ";             ' print sequence
  For y = 0 To (2^x)-1                 ' element loop
    Print AND(FUNC(_Parity(y)),1);     ' print element
  Next                                 ' next element
  Print                                ' terminate elements line
Next                                   ' next sequence

End

_Parity Param (1)                      ' parity function
  Local (1)                            ' number of bits set
  b@ = 0                               ' no bits set yet
  Do While a@ # 0                      ' until all bits are counted
    If AND (a@, 1) Then b@ = b@ + 1    ' bit set? increment count
    a@ = SHL(a@, -1)                   ' shift the number
  Loop
Return (b@)                            ' return number of bits set

Output:

 0: 0
 1: 01
 2: 0110
 3: 01101001
 4: 0110100110010110
 5: 01101001100101101001011001101001
 6: 0110100110010110100101100110100110010110011010010110100110010110

0 OK, 0:123

VBA

Option Explicit

Sub Main()
Dim i&, t$
    For i = 1 To 8
        t = Thue_Morse(t)
        Debug.Print i & ":=> " & t
    Next
End Sub

Private Function Thue_Morse(s As String) As String
Dim k$
    If s = "" Then
        k = "0"
    Else
        k = s
        k = Replace(k, "1", "2")
        k = Replace(k, "0", "1")
        k = Replace(k, "2", "0")
    End If
    Thue_Morse = s & k
End Function

Output:

1:=> 0
2:=> 01
3:=> 0110
4:=> 01101001
5:=> 0110100110010110
6:=> 01101001100101101001011001101001
7:=> 0110100110010110100101100110100110010110011010010110100110010110
8:=> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Visual Basic .NET

Translation of: C#

Imports System.Text

Module Module1

    Sub Sequence(steps As Integer)
        Dim sb1 As New StringBuilder("0")
        Dim sb2 As New StringBuilder("1")
        For index = 1 To steps
            Dim tmp = sb1.ToString
            sb1.Append(sb2)
            sb2.Append(tmp)
        Next
        Console.WriteLine(sb1)
    End Sub

    Sub Main()
        Sequence(6)
    End Sub

End Module

Output:

0110100110010110100101100110100110010110011010010110100110010110

Wren

Translation of: Kotlin

var thueMorse = Fn.new { |n|
    var sb0 = "0"
    var sb1 = "1"
    (0...n).each { |i|
        var tmp = sb0
        sb0 = sb0 + sb1
        sb1 = sb1 + tmp
    }
    return sb0
}

for (i in 0..6) System.print("%(i) : %(thueMorse.call(i))")

Output:

0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110

XLISP

(defun thue-morse (n)
    (defun flip-bits (s)
        (defun flip (l)
            (if (not (null l))
                (cons
                    (if (equal (car l) #\1)
                        #\0
                        #\1)
                    (flip (cdr l)))))
        (list->string (flip (string->list s))))
    (if (= n 0)
        "0"
        (string-append (thue-morse (- n 1)) (flip-bits (thue-morse (- n 1))))))

; define RANGE, for testing purposes

(defun range (x y)
    (if (< x y)
        (cons x (range (+ x 1) y))))

; test THUE-MORSE by printing the strings it returns for n = 0 to n = 6

(mapcar (lambda (n) (print (thue-morse n))) (range 0 7))

Output:

"0" 
"01" 
"0110" 
"01101001" 
"0110100110010110" 
"01101001100101101001011001101001" 
"0110100110010110100101100110100110010110011010010110100110010110"

XPL0

string 0;               \use zero-terminated strings
char Thue;
int  N, I, J;
[Thue:= Reserve(Free);  \reserve all available memory
Thue(0):= ^0;
J:= 1;                  \set index to terminator
for N:= 0 to 6 do
        [Thue(J):= 0;   \terminate string
        Text(0, Thue);  \show result
        CrLf(0);
        I:= 0;          \invert string and store it on the end
        repeat  Thue(J+I):= Thue(I) xor 1;
                I:= I+1;
        until   I = J;
        J:= J+I;        \set index to terminator
        ];
]

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

Yabasic

Translation of: Phix

tm$ = "0"
for i=1 to 8
    ? tm$
    tm$ = tm$ + inverte$(tm$)
next

sub inverte$(tm$)
    local i
    
    for i = 1 to len(tm$)
        mid$(tm$, i, 1) = str$(not val(mid$(tm$, i, 1)))
    next
    return tm$
end sub

Zig

const std = @import("std");

fn thueMorse(comptime T: type, n: T) bool {
    var r = n;
    var s: u8 = @sizeOf(T);
    
    while (s > 0) : (s >>= 1) r ^= std.math.shr(T, r, s);
    return r & 1 == 1;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    for (0..63) |n| 
        try stdout.writeByte(if (thueMorse(@TypeOf(n), n)) '1' else '0');
    try stdout.writeByte('\n');
}

Output:

011010011001011010010110011010011001011001101001011010011001011

zkl

fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }

"12233334444" - "23"-->"14444"

str:="0"; do(7){ str=nextTM(str.println()) }

println() returns the result it prints (as a string).

Translation of: Java

fcn nextTM2{
   var sb1=Data(Void,"0"), sb2=Data(Void,"1");
   r:=sb1.text; sb1.append(sb2); sb2.append(r);
   r
}

do(7){ nextTM2().println() }

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110