Thue-Morse: Difference between revisions

43,706 bytes added ,  2 months ago
 
(107 intermediate revisions by 46 users not shown)
Line 7:
;See also
*   YouTube entry: [https://www.youtube.com/watch?v=prh72BLNjIk The Fairest Sharing Sequence Ever]
*   YouTube entry: [https://www.youtube.com/watch?v=Tt5TTid6YXk Math and OCD - My story with the Thue-Morse sequence]
<br><br>
* &nbsp; Task: [[Fairshare between two and more]]
<br><br>
 
=={{header|11l}}==
{{trans|Python: By counting set ones in binary representation}}
 
<syntaxhighlight lang="11l">F thue_morse_digits(digits)
R (0 .< digits).map(n -> bits:popcount(n) % 2)
 
print(thue_morse_digits(20))</syntaxhighlight>
 
{{out}}
<pre>
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]
</pre>
 
=={{header|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.
 
<syntaxhighlight lang="8080asm"> 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</syntaxhighlight>
 
{{out}}
 
The line breaks are added for clarity, the program does not actually print them.
 
<pre>0110100110010110100101100110100110010110011010010110100110010110
1001011001101001011010011001011001101001100101101001011001101001
1001011001101001011010011001011001101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Action!}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Thue-Morse.png Screenshot from Atari 8-bit computer]
<pre>
T0=0
 
T1=01
 
T2=0110
 
T3=01101001
 
T4=0110100110010110
 
T5=01101001100101101001011001101001
 
T6=0110100110010110100101100110100110010110011010010110100110010110
 
T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
</pre>
 
=={{header|Ada}}==
Implementation using an L-system.
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO; use Ada.Text_IO;
 
procedure Thue_Morse is
Line 29 ⟶ 142:
Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I));
end loop;
end Thue_Morse;</langsyntaxhighlight>
 
{{out}}
Line 41 ⟶ 154:
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68"># "flips" the "bits" in a string (assumed to contain only "0" and "1" characters) #
OP FLIP = ( STRING s )STRING:
BEGIN
Line 56 ⟶ 169:
print( ( tm, newline ) );
tm +:= FLIP tm
OD</langsyntaxhighlight>
{{out}}
<pre>
Line 67 ⟶ 180:
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|APL}}==
<syntaxhighlight lang="apl">⍝ generate the first ⍵ elements of the Thue-Morse sequence
tm←{⍵⍴(⊢,~)⍣(⍵≤(⍴⊢))⊢,0}</syntaxhighlight>
{{out}}
<pre> 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</pre>
 
=={{header|AppleScript}}==
===Functional===
 
{{Trans|JavaScript}}
 
<langsyntaxhighlight AppleScriptlang="applescript">-- THUE MORSE ------------------------------------------ THUE MORSE ----------------------
 
-- thueMorse :: Int -> String
Line 89 ⟶ 210:
intercalate("", ¬
foldl(concatBinaryInverse, [0], enumFromTo(1, nCycles)))¬
enumFromTo(1, nCycles)))
end thueMorse
 
 
-- TEST --------------------------------------------- TEST -------------------------
on run
Line 102 ⟶ 224:
 
 
------------------------- GENERIC ------------------------
-- GENERIC LIBRARY FUNCTIONS
 
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m > n then
set dlst to -1{}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
set d to 1{}
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
 
 
-- foldl :: (a -> b -> a) -> a -> [b] -> a
Line 129 ⟶ 251:
end tell
end foldl
 
 
-- intercalate :: Text -> [Text] -> Text
Line 137 ⟶ 260:
return strJoined
end intercalate
 
 
-- map :: (a -> b) -> [a] -> [b]
Line 149 ⟶ 273:
end tell
end map
 
 
-- Lift 2nd class handler function into 1st class script wrapper
Line 160 ⟶ 285:
end script
end if
end mReturn</langsyntaxhighlight>
<pre>"0110100110010110100101100110100110010110011010010110100110010110"</pre>
----
 
===Idiomatic===
 
Implements the "flip previous cycles" method, stopping at a specified sequence length.
 
<syntaxhighlight lang="applescript">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))</syntaxhighlight>
 
{{output}}
<syntaxhighlight lang="applescript">"
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101"</syntaxhighlight>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">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</syntaxhighlight>
 
{{out}}
 
<pre>0
01
0110
01101001
0110100110010110
01101001100101101001011001101001</pre>
 
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">ThueMorse(num, iter){
if !iter
return num
for i, n in StrSplit(num)
opp .= !n
res := ThueMorse(num . opp, --iter)
return res
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">num := 0
loop 7
output .= A_Index-1 " : " ThueMorse(num, A_Index-1) "`n"
MsgBox % output</syntaxhighlight>
{{out}}
<pre>0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|AWK}}==
<langsyntaxhighlight AWKlang="awk">BEGIN{print x="0"}
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</langsyntaxhighlight>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
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
</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
 
==={{header|Sinclair ZX81 BASIC}}===
<langsyntaxhighlight lang="basic"> 10 LET T$="0"
20 PRINT "T0=";T$
30 FOR I=1 TO 7
Line 180 ⟶ 424:
100 NEXT J
110 PRINT T$
120 NEXT I</langsyntaxhighlight>
{{out}}
<pre>T0=0
Line 192 ⟶ 436:
 
=={{header|BBC BASIC}}==
<langsyntaxhighlight lang="bbcbasic">REM >thuemorse
tm$ = "0"
PRINT tm$
Line 207 ⟶ 451:
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"
NEXT
= previous$ + tm$</langsyntaxhighlight>
{{out}}
<pre>0
Line 218 ⟶ 462:
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|BCPL}}==
<syntaxhighlight lang="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')
$)</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Befunge}}==
{{trans|C}}
 
This implements the algorithm that counts the 1 bits in the binary representation of the sequence number.
 
<syntaxhighlight lang="befunge">:0\:!v!:\+g20\<>*:*-!#@_
86%2$_:2%02p2/^^82:+1,+*</syntaxhighlight>
 
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Binary Lambda Calculus}}==
 
The (infinite) Thue-Morse sequence is output by the 115 bit BLC program
 
<pre>0001000110100001010100011010000000000101101110000101100000010111111101011001111001111110111110000011001011010000010</pre>
 
as documented in https://github.com/tromp/AIT/blob/master/characteristic_sequences/thue-morse.lam
 
Output:
 
<pre>01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101100110100110010110100101100110100101101001...</pre>
 
=={{header|BQN}}==
<syntaxhighlight lang="bqn">TM ← {𝕩↑(⊢∾¬)⍟(1+⌈2⋆⁼𝕩)⥊0}
 
TM 25 #get first 25 elements</syntaxhighlight>
{{out}}
<pre>⟨ 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 ⟩</pre>
 
=={{header|C}}==
===C: Using string operations===
{{trans|Java}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 240 ⟶ 528:
puts(sequence);
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 248 ⟶ 536:
 
===C: By counting ones in binary representation of an iterator===
<langsyntaxhighlight Clang="c">#include <stdio.h>
 
/**
Line 272 ⟶ 560:
 
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 281 ⟶ 569:
 
===C: By counting ones in binary representation of an iterator (w/User options)===
<langsyntaxhighlight Clang="c"> #include <stdio.h>
 
/**
Line 329 ⟶ 617:
 
return 0;
} </langsyntaxhighlight>
 
{{out}}
Line 337 ⟶ 625:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">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();
}
}
}</syntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <iostream>
#include <iterator>
Line 357 ⟶ 676:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 369 ⟶ 688:
</pre>
 
=={{header|C#CLU}}==
<syntaxhighlight lang="clu">% Yields an infinite Thue-Morse sequence, digit by digit
{{trans|Java}}
tm = iter () yields (char)
<lang csharp>using System;
n: int := 1
using System.Text;
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
namespace ThueMorse
start_up = proc ()
{
classAMOUNT Program= 64
po: stream := stream$primary_output()
{
n: int := 0
static void Main(string[] args)
for c: char in {tm() do
stream$putc(po, Sequence(6c);
}n := n + 1
if n = AMOUNT then break end
end
end start_up</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|COBOL}}==
public static void Sequence(int steps)
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
{
PROGRAM-ID. THUE-MORSE.
var sb1 = new StringBuilder("0");
 
var sb2 = new StringBuilder("1");
DATA DIVISION.
for (int i = 0; i < steps; i++)
WORKING-STORAGE {SECTION.
01 var tmp = sb1STRINGS.ToString();
03 CURRENT-STATE sb1.Append PIC X(sb264);.
03 TEMP sb2.Append PIC X(tmp64);.
 
}
PROCEDURE ConsoleDIVISION.WriteLine(sb1);
ConsoleBEGIN.ReadLine();
} MOVE "0" TO CURRENT-STATE.
PERFORM THUE-MORSE-STEP 8 TIMES.
}
DISPLAY CURRENT-STATE.
}</lang>
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.</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun bit-complement (bit-vector)
(loop with result = (make-array (length bit-vector) :element-type 'bit)
for b across bit-vector
Line 421 ⟶ 772:
do (print-bit-vector value)))
 
(thue-morse 6)</langsyntaxhighlight>
{{out}}
<pre>
Line 430 ⟶ 781:
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Cowgol}}==
<syntaxhighlight lang="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();</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Crystal}}==
{{trans|Javascript}}
<syntaxhighlight lang="ruby">steps = 6
 
tmp = ""
s1 = "0"
s2 = "1"
 
steps.times {
tmp = s1
s1 += s2
s2 += tmp
}
 
puts s1</syntaxhighlight>
 
{{out}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110
</pre>
Line 435 ⟶ 830:
=={{header|D}}==
{{trans|C}}
<langsyntaxhighlight lang="d">import std.range;
import std.stdio;
 
Line 463 ⟶ 858:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 474 ⟶ 869:
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Thue-Morse#Pascal Pascal].
 
=={{header|Draco}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|EasyLang}}==
{{trans|BASIC256}}
<syntaxhighlight>
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$
.
</syntaxhighlight>
 
=={{header|Elena}}==
{{trans|C#}}
ELENA 36.2.1x :
<langsyntaxhighlight lang="elena">import extensions.;
import system'text.;
 
sequence(int steps)
program =
{
var sb1 := TextBuilder.load("0");
sequence(IntNumber steps)
var sb2 := TextBuilder.load("1");
[
for(int i := 0; vari sb1< :=steps; TextBufferi new("0").+= 1)
{
var sb2 := TextBuffer new("1").
0var till:stepstmp do(&int:i)= sb1.Value;
[sb1.write(sb2);
sb2.write(tmp)
var tmp := sb1 literal.
};
sb1 write(sb2).
console.printLine(sb1).readLine()
sb2 write(tmp).
}
].
console printLine(sb1); readLine
public program()
]
{
sequence(6)
// program entry
}</syntaxhighlight>
eval
[
$self sequence(6)
]
}.</lang>
{{out}}
<pre>
Line 507 ⟶ 945:
 
=={{header|Elixir}}==
<langsyntaxhighlight lang="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)
Line 515 ⟶ 953:
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)</langsyntaxhighlight>
 
{{out}}
<pre>
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Excel}}==
===LAMBDA===
 
Binding the name '''thueMorse''' to the following lambda expression in the Name Manager of the Excel WorkBook:
 
(See [https://www.microsoft.com/en-us/research/blog/lambda-the-ultimatae-excel-worksheet-function/ LAMBDA: The ultimate Excel worksheet function])
 
{{Works with|Office 365 betas 2021}}
<syntaxhighlight lang="lisp">thueMorse
=LAMBDA(n,
APPLYN(n)(
LAMBDA(bits,
APPENDCOLS(bits)(
LAMBDA(x,
IF(0 < x, 0, 1)
)(bits)
)
)
)(0)
)</syntaxhighlight>
 
and also assuming the following generic bindings in the Name Manager for the WorkBook:
 
<syntaxhighlight lang="lisp">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()
)
)
)
)</syntaxhighlight>
 
{{Out}}
The formula in cell B2 below defines the array of 2^5 = 32 bits which populates the range '''B2:AG2'''
 
{| class="wikitable"
|-
|||style="text-align:right; font-family:serif; font-style:italic; font-size:120%;"|fx
! colspan="33" style="text-align:left; vertical-align: bottom; font-family:Arial, Helvetica, sans-serif !important;"|=thueMorse(A2)
|- style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff;"
|
| 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
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 1
| style="font-weight:bold" | Iterations
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 2
| style="font-weight:bold" | 5
| style="text-align:center; background-color:#cbcefb" | 0
| style="text-align:center" | 1
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 1
| style="text-align:center" | 0
| style="text-align:center" | 0
| style="text-align:center" | 1
|}
 
Or, as a string, showing up to 2^6 = 64 bits:
 
{| class="wikitable"
|-
|||style="text-align:right; font-family:serif; font-style:italic; font-size:120%;"|fx
! colspan="2" style="text-align:left; vertical-align: bottom; font-family:Arial, Helvetica, sans-serif !important;"|=CONCAT(VALUETOTEXT(thueMorse(A2)))
|- style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff;"
|
| A
| B
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 1
| style="font-weight:bold" | Iterations
| style="font-weight:bold" | Thue-Morse sequence
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 2
| style="font-weight:bold" | 0
| style="background-color:#cbcefb" | 0
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 3
| style="font-weight:bold" | 1
| 01
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 4
| style="font-weight:bold" | 2
| 0110
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 5
| style="font-weight:bold" | 3
| 01101001
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 6
| style="font-weight:bold" | 4
| 0110100110010110
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 7
| style="font-weight:bold" | 5
| 01101001100101101001011001101001
|-
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 8
| style="font-weight:bold" | 6
| 0110100110010110100101100110100110010110011010010110100110010110
|}
 
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// 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 ""
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.98}}
<syntaxhighlight lang="factor">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</syntaxhighlight>
{{out}}
<pre>
Line 530 ⟶ 1,216:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<langsyntaxhighlight lang="fortran">program thue_morse
implicit none
logical :: f(32) = .false.
Line 542 ⟶ 1,228:
end do
end program thue_morse</langsyntaxhighlight>
{{out}}
<pre>
Line 552 ⟶ 1,238:
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
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
</pre>
 
 
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{output}}
<pre>
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
</pre>
 
 
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Thue-Morse}}
 
=== Solution 1 ===
 
[[File:Fōrmulæ - Thue–Morse sequence 01.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 11.png]]
 
=== Solution 2 ===
 
[[File:Fōrmulæ - Thue–Morse sequence 02.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 11.png]]
 
=== Solution 3 ===
 
[[File:Fōrmulæ - Thue–Morse sequence 03.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 11.png]]
 
=== Solution 4 ===
 
Notice that this solution generates a string.
 
[[File:Fōrmulæ - Thue–Morse sequence 04.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 12.png]]
 
=== Solution 5 ===
 
Notice that this solution generates a string.
 
[[File:Fōrmulæ - Thue–Morse sequence 05.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 12.png]]
 
=== Solution 6 ===
 
Notice that this solution generates a string.
 
[[File:Fōrmulæ - Thue–Morse sequence 06.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 12.png]]
 
=== Solution 7. L-system ===
 
There are generic functions written in Fōrmulæ to compute an L-system in the page [[L-system#Fōrmulæ | L-system]].
 
The program that creates a Hilbert curve is:
 
[[File:Fōrmulæ - L-system - Thue-Morse 01.png]]
 
[[File:Fōrmulæ - Thue–Morse sequence 12.png]]
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">// prints the first few members of the Thue-Morse sequence
 
package main
Line 585 ⟶ 1,409:
fmt.Println( tmBuffer.String() )
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 599 ⟶ 1,423:
=={{header|Haskell}}==
 
Computing progressively longer prefixes of the sequence:
<lang haskell>import Control.Monad
 
<syntaxhighlight lang="haskell">thueMorsePxs :: [[Int]]
thueMorse = ap (++) (map (1-)) `iterate` [0]</lang>
thueMorsePxs = iterate ((++) <*> map (1 -)) [0]
 
{-
'''Output:'''
= Control.Monad.ap (++) (map (1-)) `iterate` [0]
<lang haskell>~> thueMorse !! 5
= iterate (\ xs -> (++) xs (map (1-) xs)) [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]</lang>
= iterate (\ xs -> xs ++ map (1-) xs) [0]
-}
main :: IO ()
main = print $ thueMorsePxs !! 5</syntaxhighlight>
{{Out}}
<pre>[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]</pre>
 
The infinite sequence itself:
 
<syntaxhighlight lang="haskell">thueMorse :: [Int]
thueMorse = 0 : g 1
where
g i = (1 -) <$> take i thueMorse <> g (2 * i)
main :: IO ()
main = print $ take 33 thueMorse</syntaxhighlight>
{{Out}}
<pre>[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]</pre>
 
=={{header|J}}==
Line 611 ⟶ 1,454:
We only show a prefix of the sequence:
 
<langsyntaxhighlight Jlang="j"> (, -.)@]^:[&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 ...</langsyntaxhighlight>
 
Or, more compactly:
 
<langsyntaxhighlight Jlang="j"> ' '-.~":(, -.)@]^:[&0]9
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...</langsyntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">public class ThueMorse {
 
public static void main(String[] args) {
Line 636 ⟶ 1,479:
System.out.println(sb1);
}
}</langsyntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|JavaScript}}==
===ES5===
{{trans|Java}}
<syntaxhighlight lang="javascript">(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);</syntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
===ES6===
<syntaxhighlight lang="javascript">(() => {
'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();
})();</syntaxhighlight>
{{Out}}
<pre>[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]</pre>
 
=={{header|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:
<syntaxhighlight lang="text">def thueMorse:
0,
({sb0: "0", sb1: "1", n:1 }
| while( true;
{n: (.sb0|length),
sb0: (.sb0 + .sb1),
sb1: (.sb1 + .sb0)} )
| .sb0[.n:]
| explode[]
| . - 48);</syntaxhighlight>
'''Example:'''
<syntaxhighlight lang="text">[limit(100;thueMorse)] | join("")</syntaxhighlight>
{{out}}
<pre> 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110
</pre>
 
=={{header|Julia}}==
{{works with|Julia|0.6}}
 
<langsyntaxhighlight lang="julia">function thuemorse(len::Int)
rst = Vector{Int8}(len)
rst[1] = 0
Line 656 ⟶ 1,629:
end
 
println(join(thuemorse(100)))</langsyntaxhighlight>
 
{{out}}
Line 662 ⟶ 1,635:
 
=={{header|Kotlin}}==
===Kotlin: From java===
{{trans|Java}}
The original Java code, as translated to Kotlin, with a few cleanups.
<lang scala>// version 1.1.2
<syntaxhighlight lang="kotlin">fun thueMorse(n: Int): String {
val sb0 = StringBuilder("0")
val sb1 = StringBuilder("1")
repeat(0 until n).forEach {
val tmp = sb0.toString()
sb0.append(sb1)
Line 675 ⟶ 1,649:
}
 
fun main(args: Array<String>) {
for (i in 0..6) println("$i : ${thueMorse(i)}")
}</langsyntaxhighlight>
 
{{out}}
Line 690 ⟶ 1,664:
</pre>
 
===Kotlin: Alternative===
=={{header|JavaScript}}==
Same general idea as above, but using a few Kotlin specific code shortcuts.
===ES5===
<syntaxhighlight lang="kotlin">fun thueMorse(n: Int): String {
{{trans|Java}}
val pair = "0" to "1"
<lang JavaScript>(function(steps) {
repeat(n) { pair = with(pair) { first + second to second + first } }
'use strict';
return pair.first
var i, tmp, s1 = '0', s2 = '1';
}
for (i = 0; i < steps; i++) {
tmp = s1;
s1 += s2;
s2 += tmp;
}
console.log(s1);
})(6);</lang>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
fun main() {
===ES6===
for (i in 0..6) println("$i : ${thueMorse(i)}")
<lang JavaScript>(() => {
}</syntaxhighlight>
'use strict';
 
{{out}}
// THUE MORSE
<pre>
0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Lambdatalk}}==
// thueMorse :: Int -> String
<syntaxhighlight lang="scheme">
let thueMorse = nCycles => range(1, Math.abs(nCycles))
.reduce(a => a.concat(a.map(x => 1 - x)), [0])
.join('');
 
{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}
// GENERIC FUNCTION
-> 0110100110010110100101100110100110010110011010010110100110010110
 
</syntaxhighlight>
// range :: Int -> Int -> [Int]
let range = (m, n) => Array.from({
length: Math.floor((n - m)) + 1
}, (_, i) => m + i);
 
 
// TEST
 
return thueMorse(6);
 
// 0110100110010110100101100110100110010110011010010110100110010110
 
})();
</lang>
 
{{Out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Lua}}==
<langsyntaxhighlight Lualang="lua">ThueMorse = {sequence = "0"}
 
function ThueMorse:show ()
Line 759 ⟶ 1,727:
ThueMorse:show()
ThueMorse:addBlock()
end</langsyntaxhighlight>
{{out}}
<pre>0
Line 766 ⟶ 1,734:
01101001
0110100110010110</pre>
=={{header|M2000 Interpreter}}==
Adapted from Java.
===One by One===
The thuemorse lambda function return another lambda, which used to send specific part of message, until end of message (return empty string).
 
<syntaxhighlight lang="m2000 interpreter">
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 6
log$="Message :"+str$(i,0)+{
}
t$=thuemorse$(i)
do
resp$=t$(16)
if resp$<>"" then
log$=resp$+"...transmitted"+{
}
else
exit
end if
always
next i
Clipboard log$
Report log$
</syntaxhighlight>
{{out}}
<pre>
Message :0
0...transmitted
Message :1
01...transmitted
Message :2
0110...transmitted
Message :3
01101001...transmitted
Message :4
0110100110010110...transmitted
Message :5
0110100110010110...transmitted
1001011001101001...transmitted
Message :6
0110100110010110...transmitted
1001011001101001...transmitted
1001011001101001...transmitted
0110100110010110...transmitted
</pre>
 
===All together===
 
<syntaxhighlight lang="m2000 interpreter">
// copy thuemorse lambda here//
dim t$(0 to 6)
document log$
jobs=stack
For i=6 to 0
t$(i)=thuemorse$(i)
stack jobs {push i}
next i
stack jobs {
while not empty
read i
resp$=t$(i)(16)
if resp$<>"" then
log$="Message :"+str$(i,0)+{
}
log$=resp$+"...transmitted"+{
}
data i
end if
end while
}
Clipboard log$
Report log$
</syntaxhighlight>
{{out}}
<pre>
Message :0
0...transmitted
Message :1
01...transmitted
Message :2
0110...transmitted
Message :3
01101001...transmitted
Message :4
0110100110010110...transmitted
Message :5
0110100110010110...transmitted
Message :6
0110100110010110...transmitted
Message :5
1001011001101001...transmitted
Message :6
1001011001101001...transmitted
Message :6
1001011001101001...transmitted
Message :6
0110100110010110...transmitted
</pre>
 
=={{header|MACRO-11}}==
<syntaxhighlight lang="macro11"> .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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ThueMorse[Range[20]]</syntaxhighlight>
{{out}}
<pre>{1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0}</pre>
 
=={{header|MATLAB}}==
===MATLAB: By counting set ones in binary representation===
<syntaxhighlight lang="MATLAB">
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
</syntaxhighlight>
{{out}}
<pre>
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
</pre>
 
 
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (show (take 30 thue) ++ "\n")]
 
thue :: [num]
thue = 0 : 1 : concat [[x, 1-x] | x<-tl thue]</syntaxhighlight>
{{out}}
<pre>[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]</pre>
 
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">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.</syntaxhighlight>
 
=={{header|NewLISP}}==
 
<langsyntaxhighlight lang="newlisp">(define (Thue-Morse loops)
(setf TM '(0))
(println TM)
Line 784 ⟶ 1,962:
(Thue-Morse 5)
(exit)
</syntaxhighlight>
</lang>
 
{{out}}
Line 795 ⟶ 1,973:
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0)
</pre>
 
=={{header|Nim}}==
 
===Using an iterator and sequences concatenations===
<syntaxhighlight lang="nim">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</syntaxhighlight>
 
{{out}}
<pre>0
01
0110
01101001
0110100110010110
01101001100101101001011001101001</pre>
 
===Using fast sequence generation algorithm from Wikipedia===
<syntaxhighlight lang="nim">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)</syntaxhighlight>
 
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|OASYS Assembler}}==
<langsyntaxhighlight lang="oasys_oaa">; Thue-Morse sequence
 
[*'A] ; Ensure the vocabulary is not empty
Line 814 ⟶ 2,033:
%@FO> ; Reset object pointer
CR ; Line break
| ; Repeat loop</langsyntaxhighlight>
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.
 
=={{header|Objeck}}==
{{trans|Java}}
<syntaxhighlight lang="objeck">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();
}
}
</syntaxhighlight>
 
Output:
<pre>
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|OCaml}}==
===By counting ones in binary representation of an iterator===
{{trans|C}}
<syntaxhighlight lang="ocaml">(* 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 ()</syntaxhighlight>
 
 
===Using string operations===
{{trans|Objeck}}
<syntaxhighlight lang="ocaml">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);</syntaxhighlight>
 
=={{header|Pascal}}==
{{works with|Free Pascal}}
{{works with|Delphi}}
Like the C++ Version [[http://rosettacode.org/wiki/Thue-Morse#C.2B.2B]] the lenght of the sequence is given in advance.
<langsyntaxhighlight lang="pascal">Program ThueMorse;
 
function fThueMorse(maxLen: NativeInt):AnsiString;
//double by appending the flipped original 0 -> 1;1 -> 0
Line 828 ⟶ 2,114:
const
cVal0 = '^';cVal1 = 'v';// cVal0 = '0';cVal1 = '1';
 
var
pOrg,
pRpl : pCharpansiChar;
i,k,ml : NativeUInt;//MaxLen: NativeInt
Begin
Line 841 ⟶ 2,127:
//setlength only one time
setlength(result,Maxlen);
 
pOrg := @result[1];
pOrg[0] := cVal0;
IF maxlen = 1 then
EXIT;
 
pRpl := pOrg;
inc(pRpl);
Line 854 ⟶ 2,140:
i := 0;
repeat
pRpl[0] := chransichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
inc(pRpl);
inc(i);
Line 865 ⟶ 2,151:
IF k > 0 then
repeat
pRpl[0] := chransichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
inc(pRpl);
inc(i)
Line 877 ⟶ 2,163:
writeln(i:3,' ',fThueMorse(i));
fThueMorse(1 shl 30);
{$IFNDEF LINUX}readln;{$ENDIF}
end.</lang>
end.</syntaxhighlight>
{{Output}}<pre>Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi
without -O4 -> 2 secs
Line 892 ⟶ 2,179:
real 0m0.806s user 0m0.563s sys 0m0.242s</pre>
 
=={{header|Perl 6}}==
{{Worksworks with|rakudoPerl|2015-12-225.x}}
<syntaxhighlight lang="perl">sub complement
Use Ctrl-C to interrupt.
{
<lang perl6>.say for 0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *;</lang>
my $s = shift;
 
$s =~ tr/01/10/;
 
return $s;
}
 
my $str = '0';
 
for (0..6) {
say $str;
$str .= complement($str);
}
</syntaxhighlight>
{{out}}
<pre>0
0
01
0110
Line 905 ⟶ 2,206:
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
^C</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>string tm = "0"
<span style="color: #004080;">string</span> <span style="color: #000000;">tm</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0"</span>
for i=1 to 8 do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
?tm
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tm</span><span style="color: #0000FF;">)</span>
tm &= sq_sub('0'+'1',tm)
<span style="color: #000000;">tm</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tm</span><span style="color: #0000FF;">)</span>
end for</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
Line 925 ⟶ 2,227:
"01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001"
</pre>
 
=={{header|Phixmonti}}==
<syntaxhighlight lang="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</syntaxhighlight>
 
=={{header|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)
 
<syntaxhighlight lang="php"><?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;
}</syntaxhighlight>
 
{{out}}
<pre> 10 : 0110100110
20 : 01101001100101101001
30 : 011010011001011010010110011010
40 : 0110100110010110100101100110100110010110
50 : 01101001100101101001011001101001100101100110100101
60 : 011010011001011010010110011010011001011001101001011010011001
70 : 0110100110010110100101100110100110010110011010010110100110010110100101
80 : 01101001100101101001011001101001100101100110100101101001100101101001011001101001
90 : 011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110
100 : 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110</pre>
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(let R 0
(prinl R)
(for (X 1 (>= 32 X))
Line 936 ⟶ 2,290:
(bin (x| (dec (** 2 X)) R)) ) ) )
(prinl (pack 0 (bin R)))
(inc 'X X) ) )</langsyntaxhighlight>
 
=={{header|PL/M}}==
<syntaxhighlight lang="PLM">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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|PowerShell}}==
<langsyntaxhighlight lang="powershell">function New-ThueMorse ( $Digits )
{
# Start with seed 0
Line 969 ⟶ 2,350:
New-ThueMorse 5
New-ThueMorse 16
New-ThueMorse 73</langsyntaxhighlight>
{{out}}
<pre>01101
0110100110010110
0110100110010110100101100110100110010110011010010110100110010110100101100</pre>
 
=={{header|PureBasic}}==
{{trans|C}}
<syntaxhighlight lang="purebasic">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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
...fin</pre>
 
=={{header|Python}}==
===Python: By substitution===
<syntaxhighlight lang="python">
<lang Python>
m='0'
print(m)
Line 987 ⟶ 2,392:
m=m0+m
print(m)
</syntaxhighlight>
</lang>
{{out}}
<pre>0
Line 998 ⟶ 2,403:
 
===Python: By counting set ones in binary representation===
<syntaxhighlight lang="python">
<lang Python>
>>> def thue_morse_digits(digits):
... return [bin(n).count('1') % 2 for n in range(digits)]
Line 1,006 ⟶ 2,411:
 
>>>
</syntaxhighlight>
</lang>
 
===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]===
<syntaxhighlight lang="python">
<lang Python>
>>> def thue_morse_subs(chars):
... ans = '0'
Line 1,018 ⟶ 2,423:
>>> thue_morse_subs(20)
'01101001100101101001'
>>>
</syntaxhighlight>
 
===Python: By pair-wise concatenation===
<syntaxhighlight lang="python">
>>> 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'
>>>
</syntaxhighlight>
</lang>
 
=={{header|Quackery}}==
This uses the [https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Fast_sequence_generation fast sequence generation algorithm] from the wiki article.
<syntaxhighlight lang="quackery">[ [] 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</syntaxhighlight>
{{out}}
<pre>
01101001100101101001
</pre>
 
=={{header|R}}==
<syntaxhighlight lang="rsplus">
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")
</syntaxhighlight>
{{out}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))
(define (thue-morse-step (s "0"))
Line 1,032 ⟶ 2,483:
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))
 
(for-each displayln (thue-morse 7))</langsyntaxhighlight>
{{out}}
<pre>0
Line 1,041 ⟶ 2,492:
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2018.03}}
First 8 of an infinite sequence
<syntaxhighlight lang="raku" line>.say for (0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *)[^8];</syntaxhighlight>
 
{{out}}
<pre>0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
^C</pre>
 
=={{header|Refal}}==
<syntaxhighlight lang="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>;
};</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|REXX}}==
===using functions===
Programming note: &nbsp; ''pop count'' &nbsp; (or &nbsp; ''weight'') &nbsp; is the number of &nbsp; <b>1</b>'s &nbsp; bits in the binary representation of a number.
<langsyntaxhighlight lang="rexx">/*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 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 $
Line 1,056 ⟶ 2,547:
/*──────────────────────────────────────────────────────────────────────────────────────*/
$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*/</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; when using the default input:}}
<pre>
01101001100101101001011001101001100101100110100101101001100101101001011001101001
</pre>
 
===using in-line code===
<langsyntaxhighlight lang="rexx">/*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 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. */</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}} <br>
 
===using 2's complement===
Line 1,077 ⟶ 2,568:
 
Because of this, the displaying of the output lacks the granularity of the first two REXX versions.
<langsyntaxhighlight lang="rexx">/*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 6 /*Not specified? Then use the default.*/
$=0 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. */</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; when using the default input:}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110
Line 1,091 ⟶ 2,582:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
tm = "0"
see tm
Line 1,106 ⟶ 2,597:
see nl
return (previous + tm)
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,116 ⟶ 2,607:
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|RPL}}==
{{works with|HP|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
≫ '<span style="color:blue">THUEM</span>' STO
 
20 <span style="color:blue">THUEM</span>
{{out}}
<pre>
1: { 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 }
</pre>
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">puts s = "0"
6.times{puts s << s.tr("01","10")}</langsyntaxhighlight>
 
{{out}}
Line 1,132 ⟶ 2,639:
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="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));
}
}</syntaxhighlight>
 
{{out}}
<pre>
1: 0
2: 01
3: 0110
4: 01101001
5: 0110100110010110
6: 01101001100101101001011001101001
7: 0110100110010110100101100110100110010110011010010110100110010110
8: 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
</pre>
 
=={{header|Scala}}==
<syntaxhighlight lang="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)}"))</syntaxhighlight>
{{Out}} See it running in your browser by [https://scastie.scala-lang.org/rsF3Y5ABQoK0zZMMA3m6Ow Scastie (JVM)].
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func recmap(repeat, seed, transform, callback) {
func (repeat, seed) {
callback(seed)
Line 1,141 ⟶ 2,693:
}
 
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })</langsyntaxhighlight>
{{out}}
<pre>
Line 1,155 ⟶ 2,707:
=={{header|SQL}}==
This example is using SQLite.
<langsyntaxhighlight SQLlang="sql">with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;</langsyntaxhighlight>
You can add a LIMIT clause to the end to limit how many lines of output you want.
 
Line 1,162 ⟶ 2,714:
Since <tt>string map</tt> correctly handles overlapping replacements, the simple map <tt>0 -> 01; 1 -> 10</tt> can be applied with no special handling:
 
<langsyntaxhighlight Tcllang="tcl">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}
Line 1,172 ⟶ 2,724:
}
return $s
}</langsyntaxhighlight>
 
Testing:
 
<langsyntaxhighlight Tcllang="tcl">for {set i 0} {$i <= 6} {incr i} {
puts [tm $i]
}</langsyntaxhighlight>
 
{{out}}
Line 1,191 ⟶ 2,743:
For giggles, also note that the above SQL solution can be "natively" applied in Tcl8.5+, which bundles Sqlite as a core extension:
 
<syntaxhighlight lang="tcl">
<lang Tcl>
package require sqlite3 ;# available with Tcl8.5+ core
sqlite3 db "" ;# create in-memory database
Line 1,197 ⟶ 2,749:
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
}</langsyntaxhighlight>
 
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">For x = 0 to 6 ' sequence loop
Print Using "_#";x;": "; ' print sequence
For y = 0 To (2^x)-1 ' element loop
Line 1,217 ⟶ 2,769:
a@ = SHL(a@, -1) ' shift the number
Loop
Return (b@) ' return number of bits set</langsyntaxhighlight>
{{Out}}
<pre> 0: 0
Line 1,228 ⟶ 2,780:
 
0 OK, 0:123</pre>
 
=={{header|VBA}}==
<syntaxhighlight lang="vb">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</syntaxhighlight>
{{Out}}
<pre>1:=> 0
2:=> 01
3:=> 0110
4:=> 01101001
5:=> 0110100110010110
6:=> 01101001100101101001011001101001
7:=> 0110100110010110100101100110100110010110011010010110100110010110
8:=> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">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))")</syntaxhighlight>
 
{{out}}
<pre>
0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|XLISP}}==
<langsyntaxhighlight lang="lisp">(defun thue-morse (n)
(defun flip-bits (s)
(defun flip (l)
Line 1,251 ⟶ 2,888:
; 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))</langsyntaxhighlight>
{{out}}
<pre>"0"
Line 1,260 ⟶ 2,897:
"01101001100101101001011001101001"
"0110100110010110100101100110100110010110011010010110100110010110"</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="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
];
]</syntaxhighlight>
 
{{out}}
<pre>
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
 
=={{header|Yabasic}}==
{{trans|Phix}}
<syntaxhighlight lang="yabasic">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</syntaxhighlight>
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }</langsyntaxhighlight>
"12233334444" - "23"-->"14444"
<langsyntaxhighlight lang="zkl">str:="0"; do(7){ str=nextTM(str.println()) }</langsyntaxhighlight>
println() returns the result it prints (as a string).
{{trans|Java}}
<langsyntaxhighlight lang="zkl">fcn nextTM2{
var sb1=Data(Void,"0"), sb2=Data(Void,"1");
r:=sb1.text; sb1.append(sb2); sb2.append(r);
r
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">do(7){ nextTM2().println() }</langsyntaxhighlight>
{{out}}
<pre>
2,172

edits