Thue-Morse: Difference between revisions
→{{header|F_Sharp|F#}}
| (127 intermediate revisions by 56 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]
* 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.
<syntaxhighlight lang="ada">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;</syntaxhighlight>
{{out}}
<pre> 0: 0
1: 01
2: 0110
3: 01101001
4: 0110100110010110
5: 01101001100101101001011001101001
6: 0110100110010110100101100110100110010110011010010110100110010110</pre>
=={{header|ALGOL 68}}==
<
OP FLIP = ( STRING s )STRING:
BEGIN
Line 25 ⟶ 169:
print( ( tm, newline ) );
tm +:= FLIP tm
OD</
{{out}}
<pre>
Line 36 ⟶ 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}}
<syntaxhighlight lang="applescript">------------------------ THUE MORSE ----------------------
-- thueMorse :: Int -> String
on thueMorse(nCycles)
script concatBinaryInverse
on
script binaryInverse
on
1 - x
end
end script
xs & map(binaryInverse, xs)
end
end script
intercalate("", ¬
foldl(concatBinaryInverse, [0],
enumFromTo(1, nCycles)))
end thueMorse
--------------------------- TEST -------------------------
on run
Line 69 ⟶ 224:
------------------------- GENERIC ------------------------
--
on
set lst to {}
repeat with i from
set end of lst to
end repeat
{}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
Line 89 ⟶ 246:
set lng to length of xs
repeat with i from 1 to lng
set v to
end repeat
return v
end tell
end foldl
-- intercalate :: Text -> [Text] -> Text
Line 103 ⟶ 261:
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell
set lng to length of xs
set
repeat with i from 1 to lng
set end of lst to
end
end map
-- Lift 2nd class handler function into 1st class script wrapper
Line 124 ⟶ 282:
else
script
property
end script
end if
end mReturn</
<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}}==
<
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</
=={{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}}===
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>T0=0
T1=01
T2=0110
T3=01101001
T4=0110100110010110
T5=01101001100101101001011001101001
T6=0110100110010110100101100110100110010110011010010110100110010110
T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001</pre>
=={{header|BBC BASIC}}==
<
tm$ = "0"
PRINT tm$
Line 151 ⟶ 451:
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"
NEXT
= previous$ + tm$</
{{out}}
<pre>0
Line 162 ⟶ 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}}
<
#include <stdlib.h>
#include <string.h>
Line 183 ⟶ 528:
puts(sequence);
return 0;
}</
{{out}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
</pre>
===C: By counting ones in binary representation of an iterator===
<syntaxhighlight lang="c">#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;
}</syntaxhighlight>
{{out}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
</pre>
===C: By counting ones in binary representation of an iterator (w/User options)===
<syntaxhighlight lang="c"> #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;
} </syntaxhighlight>
{{out}}
<pre>
Sequence length: 256
(a)lpha or (b)inary: b
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++}}==
<
#include <iostream>
#include <iterator>
Line 208 ⟶ 676:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 217 ⟶ 685:
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
=={{header|COBOL}}==
<syntaxhighlight lang="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.</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
=={{header|Common Lisp}}==
<syntaxhighlight lang="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)</syntaxhighlight>
{{out}}
<pre>
0
01
0110
01101001
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 222 ⟶ 830:
=={{header|D}}==
{{trans|C}}
<
import std.stdio;
Line 250 ⟶ 858:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 259 ⟶ 867:
0110100110010110
01101001100101101001011001101001
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 6.x :
<syntaxhighlight lang="elena">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)
}</syntaxhighlight>
{{out}}
<pre>
0110100110010110100101100110100110010110011010010110100110010110
</pre>
=={{header|Elixir}}==
<
IO.puts s
s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end)
Line 271 ⟶ 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)</
{{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 286 ⟶ 1,216:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
logical :: f(32) = .false.
integer ::
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</
{{out}}
<pre>
Line 307 ⟶ 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}}==
<
package main
Line 340 ⟶ 1,409:
fmt.Println( tmBuffer.String() )
}
}</
{{out}}
<pre>
Line 354 ⟶ 1,423:
=={{header|Haskell}}==
Computing progressively longer prefixes of the sequence:
<syntaxhighlight lang="haskell">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</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 366 ⟶ 1,454:
We only show a prefix of the sequence:
<
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:
<
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...</
=={{header|Java}}==
<
public static void main(String[] args) {
Line 391 ⟶ 1,479:
System.out.println(sb1);
}
}</
<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===
<
'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
//
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}}
<syntaxhighlight lang="julia">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)))</syntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110</pre>
=={{header|Kotlin}}==
===Kotlin: From java===
{{trans|Java}}
The original Java code, as translated to Kotlin, with a few cleanups.
<syntaxhighlight lang="kotlin">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)}")
}</syntaxhighlight>
{{out}}
<pre>
0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110
</pre>
===Kotlin: Alternative===
Same general idea as above, but using a few Kotlin specific code shortcuts.
<syntaxhighlight lang="kotlin">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)}")
}</syntaxhighlight>
{{out}}
<pre>
0 : 0
1 : 01
2 : 0110
3 : 01101001
4 : 0110100110010110
5 : 01101001100101101001011001101001
6 : 0110100110010110100101100110100110010110011010010110100110010110
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{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
</syntaxhighlight>
=={{header|Lua}}==
<
function ThueMorse:show ()
Line 451 ⟶ 1,727:
ThueMorse:show()
ThueMorse:addBlock()
end</
{{out}}
<pre>0
Line 458 ⟶ 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}}==
<
(setf TM '(0))
(println TM)
Line 476 ⟶ 1,962:
(Thue-Morse 5)
(exit)
</syntaxhighlight>
{{out}}
Line 487 ⟶ 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}}==
<
[*'A] ; Ensure the vocabulary is not empty
Line 506 ⟶ 2,033:
%@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.
=={{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.
<
function fThueMorse(maxLen: NativeInt):AnsiString;
//double by appending the flipped original 0 -> 1;1 -> 0
Line 520 ⟶ 2,114:
const
cVal0 = '^';cVal1 = 'v';// cVal0 = '0';cVal1 = '1';
var
pOrg,
pRpl :
i,k,ml : NativeUInt;//MaxLen: NativeInt
Begin
Line 533 ⟶ 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 546 ⟶ 2,140:
i := 0;
repeat
pRpl[0] :=
inc(pRpl);
inc(i);
Line 557 ⟶ 2,151:
IF k > 0 then
repeat
pRpl[0] :=
inc(pRpl);
inc(i)
Line 569 ⟶ 2,163:
writeln(i:3,' ',fThueMorse(i));
fThueMorse(1 shl 30);
{$IFNDEF LINUX}readln;{$ENDIF}
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 584 ⟶ 2,179:
real 0m0.806s user 0m0.563s sys 0m0.242s</pre>
=={{header|Perl
{{
<syntaxhighlight lang="perl">sub complement
{
my $s = shift;
$s =~ tr/01/10/;
return $s;
}
my $str = '0';
for (0..6) {
say $str;
$str .= complement($str);
}
</syntaxhighlight>
{{out}}
<pre>
0
01
0110
Line 597 ⟶ 2,206:
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #004080;">string</span> <span style="color: #000000;">tm</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0"</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
"0"
"01"
"0110"
"01101001"
"0110100110010110"
"01101001100101101001011001101001"
"0110100110010110100101100110100110010110011010010110100110010110"
"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}}==
<
(prinl R)
(for (X 1 (>= 32 X))
Line 610 ⟶ 2,290:
(bin (x| (dec (** 2 X)) R)) ) ) )
(prinl (pack 0 (bin R)))
(inc 'X X) ) )</
=={{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}}==
<
{
# Start with seed 0
Line 643 ⟶ 2,350:
New-ThueMorse 5
New-ThueMorse 16
New-ThueMorse 73</
{{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">
m='0'
print(m)
Line 661 ⟶ 2,392:
m=m0+m
print(m)
</syntaxhighlight>
{{out}}
<pre>0
Line 672 ⟶ 2,403:
===Python: By counting set ones in binary representation===
<syntaxhighlight lang="python">
>>> def thue_morse_digits(digits):
... return [bin(n).count('1') % 2 for n in range(digits)]
Line 680 ⟶ 2,411:
>>>
</syntaxhighlight>
===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]===
<syntaxhighlight lang="python">
>>> def thue_morse_subs(chars):
... ans = '0'
Line 692 ⟶ 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>
=={{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}}==
<
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))
(define (thue-morse-step (s "0"))
Line 706 ⟶ 2,483:
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))
(for-each displayln (thue-morse 7))</
{{out}}
<pre>0
Line 715 ⟶ 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: ''pop count'' (or ''weight'') is the number of <b>1</b>'s bits in the binary representation of a number.
<
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N=
$= /*the Thue─Morse sequence (so far). */
do j=0 to N /*generate sequence up to the Nth item.*/
$= $ || $weight(j) // 2
end /*j*/
say $
Line 730 ⟶ 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*/</
<pre>
01101001100101101001011001101001100101100110100101101001100101101001011001101001
</pre>
===using in-line code===
<
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N=
$= /*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)
end /*j*/
say $ /*stick a fork in it, we're all done. */</
===using 2's complement===
Line 751 ⟶ 2,568:
Because of this, the displaying of the output lacks the granularity of the first two REXX versions.
<
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N=
$=
do j=1 for N /*generate sequence up to the Nth item.*/
$= $ || translate($, 10, 01)
end /*j*/
say $ /*stick a fork in it, we're all done. */</
<pre>
0110100110010110100101100110100110010110011010010110100110010110
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="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)
</syntaxhighlight>
Output:
<pre>
0
01
0110
01101001
0110100110010110
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}}==
<
6.times{puts s << s.tr("01","10")}</
{{out}}
Line 778 ⟶ 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}}==
<
func (repeat, seed) {
callback(seed)
Line 787 ⟶ 2,693:
}
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })</
{{out}}
<pre>
Line 801 ⟶ 2,707:
=={{header|SQL}}==
This example is using SQLite.
<
You can add a LIMIT clause to the end to limit how many lines of output you want.
Line 808 ⟶ 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:
<
# this could also be written as:
# interp alias {} tm_expand {} string map {0 01 1 10}
Line 818 ⟶ 2,724:
}
return $s
}</
Testing:
<
puts [tm $i]
}</
{{out}}
Line 837 ⟶ 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">
package require sqlite3 ;# available with Tcl8.5+ core
sqlite3 db "" ;# create in-memory database
Line 843 ⟶ 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
}</
=={{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
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</syntaxhighlight>
{{Out}}
<pre> 0: 0
1: 01
2: 0110
3: 01101001
4: 0110100110010110
5: 01101001100101101001011001101001
6: 0110100110010110100101100110100110010110011010010110100110010110
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}}==
<
(defun flip-bits (s)
(defun flip (l)
Line 868 ⟶ 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))</
{{out}}
<pre>"0"
Line 877 ⟶ 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}}==
<
"12233334444" - "23"-->"14444"
<
println() returns the result it prints (as a string).
{{trans|Java}}
<
var sb1=Data(Void,"0"), sb2=Data(Void,"1");
r:=sb1.text; sb1.append(sb2); sb2.append(r);
r
}</
<
{{out}}
<pre>
| |||