Thue-Morse: Difference between revisions
m →Excel LAMBDA: Added a further iteration to the second example |
|||
(43 intermediate revisions by 20 users not shown) | |||
Line 14: | Line 14: | ||
{{trans|Python: By counting set ones in binary representation}} |
{{trans|Python: By counting set ones in binary representation}} |
||
< |
<syntaxhighlight lang="11l">F thue_morse_digits(digits) |
||
R (0 .< digits).map(n -> |
R (0 .< digits).map(n -> bits:popcount(n) % 2) |
||
print(thue_morse_digits(20))</ |
print(thue_morse_digits(20))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 41: | Line 41: | ||
after all, XOR is commutative. |
after all, XOR is commutative. |
||
< |
<syntaxhighlight lang="8080asm"> org 100h |
||
;;; Write 256 bytes of ASCII '0' starting at address 200h |
;;; Write 256 bytes of ASCII '0' starting at address 200h |
||
lxi h,200h ; The array is page-aligned so L starts at 0 |
lxi h,200h ; The array is page-aligned so L starts at 0 |
||
Line 58: | Line 58: | ||
mvi c,9 ; Syscall 9 = print string |
mvi c,9 ; Syscall 9 = print string |
||
lxi d,200h ; The string is at 200h |
lxi d,200h ; The string is at 200h |
||
jmp 5</ |
jmp 5</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 68: | Line 68: | ||
1001011001101001011010011001011001101001100101101001011001101001 |
1001011001101001011010011001011001101001100101101001011001101001 |
||
0110100110010110100101100110100110010110011010010110100110010110</pre> |
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}}== |
=={{header|Ada}}== |
||
Implementation using an L-system. |
Implementation using an L-system. |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Thue_Morse is |
procedure Thue_Morse is |
||
Line 89: | Line 142: | ||
Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I)); |
Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I)); |
||
end loop; |
end loop; |
||
end Thue_Morse;</ |
end Thue_Morse;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 101: | Line 154: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68"># "flips" the "bits" in a string (assumed to contain only "0" and "1" characters) # |
||
OP FLIP = ( STRING s )STRING: |
OP FLIP = ( STRING s )STRING: |
||
BEGIN |
BEGIN |
||
Line 116: | Line 169: | ||
print( ( tm, newline ) ); |
print( ( tm, newline ) ); |
||
tm +:= FLIP tm |
tm +:= FLIP tm |
||
OD</ |
OD</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 127: | Line 180: | ||
0110100110010110100101100110100110010110011010010110100110010110 |
0110100110010110100101100110100110010110011010010110100110010110 |
||
</pre> |
</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}}== |
=={{header|AppleScript}}== |
||
Line 133: | Line 193: | ||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
< |
<syntaxhighlight lang="applescript">------------------------ THUE MORSE ---------------------- |
||
-- thueMorse :: Int -> String |
-- thueMorse :: Int -> String |
||
Line 225: | Line 285: | ||
end script |
end script |
||
end if |
end if |
||
end mReturn</ |
end mReturn</syntaxhighlight> |
||
<pre>"0110100110010110100101100110100110010110011010010110100110010110"</pre> |
<pre>"0110100110010110100101100110100110010110011010010110100110010110"</pre> |
||
---- |
---- |
||
Line 233: | Line 293: | ||
Implements the "flip previous cycles" method, stopping at a specified sequence length. |
Implements the "flip previous cycles" method, stopping at a specified sequence length. |
||
< |
<syntaxhighlight lang="applescript">on ThueMorse(sequenceLength) |
||
if (sequenceLength < 1) then return "" |
if (sequenceLength < 1) then return "" |
||
Line 262: | Line 322: | ||
end ThueMorse |
end ThueMorse |
||
return linefeed & ThueMorse(64) & (linefeed & ThueMorse(65))</ |
return linefeed & ThueMorse(64) & (linefeed & ThueMorse(65))</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight lang="applescript">" |
||
0110100110010110100101100110100110010110011010010110100110010110 |
0110100110010110100101100110100110010110011010010110100110010110 |
||
01101001100101101001011001101001100101100110100101101001100101101"</ |
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}}== |
=={{header|AWK}}== |
||
< |
<syntaxhighlight lang="awk">BEGIN{print x="0"} |
||
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</ |
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</syntaxhighlight> |
||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|BASIC256}}=== |
==={{header|BASIC256}}=== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
<syntaxhighlight lang="basic256"> |
|||
<lang BASIC256> |
|||
tm = "0" |
tm = "0" |
||
Line 297: | Line 406: | ||
Next j |
Next j |
||
End |
End |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 304: | Line 413: | ||
==={{header|Sinclair ZX81 BASIC}}=== |
==={{header|Sinclair ZX81 BASIC}}=== |
||
< |
<syntaxhighlight lang="basic"> 10 LET T$="0" |
||
20 PRINT "T0=";T$ |
20 PRINT "T0=";T$ |
||
30 FOR I=1 TO 7 |
30 FOR I=1 TO 7 |
||
Line 315: | Line 424: | ||
100 NEXT J |
100 NEXT J |
||
110 PRINT T$ |
110 PRINT T$ |
||
120 NEXT I</ |
120 NEXT I</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>T0=0 |
<pre>T0=0 |
||
Line 327: | Line 436: | ||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
< |
<syntaxhighlight lang="bbcbasic">REM >thuemorse |
||
tm$ = "0" |
tm$ = "0" |
||
PRINT tm$ |
PRINT tm$ |
||
Line 342: | Line 451: | ||
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1" |
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1" |
||
NEXT |
NEXT |
||
= previous$ + tm$</ |
= previous$ + tm$</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 355: | Line 464: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">get "libhdr" |
||
let parity(x) = |
let parity(x) = |
||
Line 364: | Line 473: | ||
$( for i=0 to 63 do writen(parity(i)) |
$( for i=0 to 63 do writen(parity(i)) |
||
wrch('*N') |
wrch('*N') |
||
$)</ |
$)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
Line 373: | Line 482: | ||
This implements the algorithm that counts the 1 bits in the binary representation of the sequence number. |
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,+*</ |
86%2$_:2%02p2/^^82:+1,+*</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110</pre> |
<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}}== |
=={{header|C}}== |
||
===C: Using string operations=== |
===C: Using string operations=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 400: | Line 528: | ||
puts(sequence); |
puts(sequence); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 408: | Line 536: | ||
===C: By counting ones in binary representation of an iterator=== |
===C: By counting ones in binary representation of an iterator=== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
/** |
/** |
||
Line 432: | Line 560: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 441: | Line 569: | ||
===C: By counting ones in binary representation of an iterator (w/User options)=== |
===C: By counting ones in binary representation of an iterator (w/User options)=== |
||
< |
<syntaxhighlight lang="c"> #include <stdio.h> |
||
/** |
/** |
||
Line 489: | Line 617: | ||
return 0; |
return 0; |
||
} </ |
} </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 500: | Line 628: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Text; |
using System.Text; |
||
Line 526: | Line 654: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
#include <iterator> |
#include <iterator> |
||
Line 548: | Line 676: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 559: | Line 687: | ||
0110100110010110100101100110100110010110011010010110100110010110 |
0110100110010110100101100110100110010110011010010110100110010110 |
||
</pre> |
</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}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun bit-complement (bit-vector) |
||
(loop with result = (make-array (length bit-vector) :element-type 'bit) |
(loop with result = (make-array (length bit-vector) :element-type 'bit) |
||
for b across bit-vector |
for b across bit-vector |
||
Line 581: | Line 772: | ||
do (print-bit-vector value))) |
do (print-bit-vector value))) |
||
(thue-morse 6)</ |
(thue-morse 6)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 592: | Line 783: | ||
0110100110010110100101100110100110010110011010010110100110010110 |
0110100110010110100101100110100110010110011010010110100110010110 |
||
</pre> |
</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}}== |
=={{header|Crystal}}== |
||
{{trans|Javascript}} |
{{trans|Javascript}} |
||
< |
<syntaxhighlight lang="ruby">steps = 6 |
||
tmp = "" |
tmp = "" |
||
Line 607: | Line 821: | ||
} |
} |
||
puts s1</ |
puts s1</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 616: | Line 830: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="d">import std.range; |
||
import std.stdio; |
import std.stdio; |
||
Line 644: | Line 858: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 658: | Line 872: | ||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
See [https://rosettacode.org/wiki/Thue-Morse#Pascal Pascal]. |
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}}== |
=={{header|Elena}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
ELENA |
ELENA 6.x : |
||
< |
<syntaxhighlight lang="elena">import extensions; |
||
import system'text; |
import system'text; |
||
Line 669: | Line 926: | ||
var sb1 := TextBuilder.load("0"); |
var sb1 := TextBuilder.load("0"); |
||
var sb2 := TextBuilder.load("1"); |
var sb2 := TextBuilder.load("1"); |
||
for(int i := 0 |
for(int i := 0; i < steps; i += 1) |
||
{ |
{ |
||
var tmp := sb1.Value; |
var tmp := sb1.Value; |
||
Line 681: | Line 938: | ||
{ |
{ |
||
sequence(6) |
sequence(6) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 688: | Line 945: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">Enum.reduce(0..6, '0', fn _,s -> |
||
IO.puts s |
IO.puts s |
||
s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) |
s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) |
||
Line 696: | Line 953: | ||
Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end) |
Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end) |
||
|> Enum.take(7) |
|> Enum.take(7) |
||
|> Enum.each(&IO.puts/1)</ |
|> Enum.each(&IO.puts/1)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 717: | Line 974: | ||
{{Works with|Office 365 betas 2021}} |
{{Works with|Office 365 betas 2021}} |
||
< |
<syntaxhighlight lang="lisp">thueMorse |
||
=LAMBDA(n, |
=LAMBDA(n, |
||
APPLYN(n)( |
APPLYN(n)( |
||
Line 728: | Line 985: | ||
) |
) |
||
)(0) |
)(0) |
||
)</ |
)</syntaxhighlight> |
||
and also assuming the following generic bindings in the Name Manager for the WorkBook: |
and also assuming the following generic bindings in the Name Manager for the WorkBook: |
||
< |
<syntaxhighlight lang="lisp">APPLYN |
||
=LAMBDA(n, |
=LAMBDA(n, |
||
LAMBDA(f, |
LAMBDA(f, |
||
Line 764: | Line 1,021: | ||
) |
) |
||
) |
) |
||
)</ |
)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 880: | Line 1,137: | ||
|} |
|} |
||
Or, as a string: |
Or, as a string, showing up to 2^6 = 64 bits: |
||
{| class="wikitable" |
{| class="wikitable" |
||
Line 893: | Line 1,150: | ||
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 1 |
| 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" | Iterations |
||
| style="font-weight:bold" | Thue |
| 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="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 |
| 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}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
< |
<syntaxhighlight lang="factor">USING: io kernel math math.parser sequences ; |
||
: thue-morse ( seq n -- seq' ) |
: thue-morse ( seq n -- seq' ) |
||
Line 909: | Line 1,202: | ||
: print-tm ( seq -- ) [ number>string ] map "" join print ; |
: print-tm ( seq -- ) [ number>string ] map "" join print ; |
||
7 <iota> [ { 0 } swap thue-morse print-tm ] each</ |
7 <iota> [ { 0 } swap thue-morse print-tm ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 923: | Line 1,216: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
< |
<syntaxhighlight lang="fortran">program thue_morse |
||
implicit none |
implicit none |
||
logical :: f(32) = .false. |
logical :: f(32) = .false. |
||
Line 935: | Line 1,228: | ||
end do |
end do |
||
end program thue_morse</ |
end program thue_morse</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 947: | Line 1,240: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic"> |
||
Dim As String tm = "0" |
Dim As String tm = "0" |
||
Line 968: | Line 1,261: | ||
Next j |
Next j |
||
End |
End |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 980: | Line 1,273: | ||
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 |
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 |
||
</pre> |
</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}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">// prints the first few members of the Thue-Morse sequence |
||
package main |
package main |
||
Line 1,013: | Line 1,409: | ||
fmt.Println( tmBuffer.String() ) |
fmt.Println( tmBuffer.String() ) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,029: | Line 1,425: | ||
Computing progressively longer prefixes of the sequence: |
Computing progressively longer prefixes of the sequence: |
||
< |
<syntaxhighlight lang="haskell">thueMorsePxs :: [[Int]] |
||
thueMorsePxs = iterate ((++) <*> map (1 -)) [0] |
thueMorsePxs = iterate ((++) <*> map (1 -)) [0] |
||
Line 1,038: | Line 1,434: | ||
-} |
-} |
||
main :: IO () |
main :: IO () |
||
main = print $ thueMorsePxs !! 5</ |
main = print $ thueMorsePxs !! 5</syntaxhighlight> |
||
{{Out}} |
{{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> |
<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> |
||
Line 1,044: | Line 1,440: | ||
The infinite sequence itself: |
The infinite sequence itself: |
||
< |
<syntaxhighlight lang="haskell">thueMorse :: [Int] |
||
thueMorse = 0 : g 1 |
thueMorse = 0 : g 1 |
||
where |
where |
||
Line 1,050: | Line 1,446: | ||
main :: IO () |
main :: IO () |
||
main = print $ take 33 thueMorse</ |
main = print $ take 33 thueMorse</syntaxhighlight> |
||
{{Out}} |
{{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> |
<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> |
||
Line 1,058: | Line 1,454: | ||
We only show a prefix of the sequence: |
We only show a prefix of the sequence: |
||
< |
<syntaxhighlight lang="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 ...</ |
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 ...</syntaxhighlight> |
||
Or, more compactly: |
Or, more compactly: |
||
< |
<syntaxhighlight lang="j"> ' '-.~":(, -.)@]^:[&0]9 |
||
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...</ |
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class ThueMorse { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
Line 1,083: | Line 1,479: | ||
System.out.println(sb1); |
System.out.println(sb1); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
Line 1,089: | Line 1,485: | ||
===ES5=== |
===ES5=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="javascript">(function(steps) { |
||
'use strict'; |
'use strict'; |
||
var i, tmp, s1 = '0', s2 = '1'; |
var i, tmp, s1 = '0', s2 = '1'; |
||
Line 1,098: | Line 1,494: | ||
} |
} |
||
console.log(s1); |
console.log(s1); |
||
})(6);</ |
})(6);</syntaxhighlight> |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
===ES6=== |
===ES6=== |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,191: | Line 1,587: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{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> |
<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}}== |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">function thuemorse(len::Int) |
||
rst = Vector{Int8}(len) |
rst = Vector{Int8}(len) |
||
rst[1] = 0 |
rst[1] = 0 |
||
Line 1,212: | Line 1,629: | ||
end |
end |
||
println(join(thuemorse(100)))</ |
println(join(thuemorse(100)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,221: | Line 1,638: | ||
{{trans|Java}} |
{{trans|Java}} |
||
The original Java code, as translated to Kotlin, with a few cleanups. |
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 sb0 = StringBuilder("0") |
||
val sb1 = StringBuilder("1") |
val sb1 = StringBuilder("1") |
||
Line 1,234: | Line 1,651: | ||
fun main() { |
fun main() { |
||
for (i in 0..6) println("$i : ${thueMorse(i)}") |
for (i in 0..6) println("$i : ${thueMorse(i)}") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,249: | Line 1,666: | ||
===Kotlin: Alternative=== |
===Kotlin: Alternative=== |
||
Same general idea as above, but using a few Kotlin specific code shortcuts. |
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" |
val pair = "0" to "1" |
||
repeat(n) { pair = with(pair) { first + second to second + first } } |
repeat(n) { pair = with(pair) { first + second to second + first } } |
||
Line 1,257: | Line 1,674: | ||
fun main() { |
fun main() { |
||
for (i in 0..6) println("$i : ${thueMorse(i)}") |
for (i in 0..6) println("$i : ${thueMorse(i)}") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,271: | Line 1,688: | ||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
{def thue_morse |
{def thue_morse |
||
Line 1,286: | Line 1,703: | ||
-> 0110100110010110100101100110100110010110011010010110100110010110 |
-> 0110100110010110100101100110100110010110011010010110100110010110 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">ThueMorse = {sequence = "0"} |
||
function ThueMorse:show () |
function ThueMorse:show () |
||
Line 1,310: | Line 1,727: | ||
ThueMorse:show() |
ThueMorse:show() |
||
ThueMorse:addBlock() |
ThueMorse:addBlock() |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 1,317: | Line 1,734: | ||
01101001 |
01101001 |
||
0110100110010110</pre> |
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"> |
|||
=={{header|Mathematica}}== |
|||
thuemorse$=lambda$ (n as integer)->{ |
|||
<lang Mathematica>ThueMorse[Range[20]]</lang> |
|||
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}} |
{{out}} |
||
<pre>{1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0}</pre> |
<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}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">MODULE ThueMorse; |
||
FROM Strings IMPORT Concat; |
FROM Strings IMPORT Concat; |
||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
||
Line 1,349: | Line 1,943: | ||
Sequence(6); |
Sequence(6); |
||
ReadChar; |
ReadChar; |
||
END ThueMorse.</ |
END ThueMorse.</syntaxhighlight> |
||
=={{header|NewLISP}}== |
=={{header|NewLISP}}== |
||
< |
<syntaxhighlight lang="newlisp">(define (Thue-Morse loops) |
||
(setf TM '(0)) |
(setf TM '(0)) |
||
(println TM) |
(println TM) |
||
Line 1,368: | Line 1,962: | ||
(Thue-Morse 5) |
(Thue-Morse 5) |
||
(exit) |
(exit) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,383: | Line 1,977: | ||
===Using an iterator and sequences concatenations=== |
===Using an iterator and sequences concatenations=== |
||
< |
<syntaxhighlight lang="nim">import sequtils, strutils |
||
iterator thueMorse(maxSteps = int.high): string = |
iterator thueMorse(maxSteps = int.high): string = |
||
Line 1,395: | Line 1,989: | ||
for bits in thueMorse(6): |
for bits in thueMorse(6): |
||
echo bits</ |
echo bits</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,406: | Line 2,000: | ||
===Using fast sequence generation algorithm from Wikipedia=== |
===Using fast sequence generation algorithm from Wikipedia=== |
||
< |
<syntaxhighlight lang="nim">type Bit = 0..1 |
||
proc thueMorse(seqLength: Positive): string = |
proc thueMorse(seqLength: Positive): string = |
||
Line 1,416: | Line 2,010: | ||
result.add chr(val + ord('0')) |
result.add chr(val + ord('0')) |
||
echo thueMorse(64)</ |
echo thueMorse(64)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,422: | Line 2,016: | ||
=={{header|OASYS Assembler}}== |
=={{header|OASYS Assembler}}== |
||
< |
<syntaxhighlight lang="oasys_oaa">; Thue-Morse sequence |
||
[*'A] ; Ensure the vocabulary is not empty |
[*'A] ; Ensure the vocabulary is not empty |
||
Line 1,439: | Line 2,033: | ||
%@FO> ; Reset object pointer |
%@FO> ; Reset object pointer |
||
CR ; Line break |
CR ; Line break |
||
| ; Repeat loop</ |
| ; Repeat loop</syntaxhighlight> |
||
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. |
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}}== |
=={{header|Objeck}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">class ThueMorse { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
Sequence(6); |
Sequence(6); |
||
Line 1,460: | Line 2,054: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 1,470: | Line 2,064: | ||
===By counting ones in binary representation of an iterator=== |
===By counting ones in binary representation of an iterator=== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="ocaml">(* description: Counts the number of bits set to 1 |
||
input: the number to have its bit counted |
input: the number to have its bit counted |
||
output: the number of bits set to 1 *) |
output: the number of bits set to 1 *) |
||
Line 1,488: | Line 2,082: | ||
| _ -> assert false) |
| _ -> assert false) |
||
done; |
done; |
||
print_newline ()</ |
print_newline ()</syntaxhighlight> |
||
===Using string operations=== |
===Using string operations=== |
||
{{trans|Objeck}} |
{{trans|Objeck}} |
||
< |
<syntaxhighlight lang="ocaml">let sequence steps = |
||
let sb1 = Buffer.create 100 in |
let sb1 = Buffer.create 100 in |
||
let sb2 = Buffer.create 100 in |
let sb2 = Buffer.create 100 in |
||
Line 1,506: | Line 2,100: | ||
let () = |
let () = |
||
print_endline (sequence 6);</ |
print_endline (sequence 6);</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
Line 1,512: | Line 2,106: | ||
{{works with|Delphi}} |
{{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. |
Like the C++ Version [[http://rosettacode.org/wiki/Thue-Morse#C.2B.2B]] the lenght of the sequence is given in advance. |
||
< |
<syntaxhighlight lang="pascal">Program ThueMorse; |
||
function fThueMorse(maxLen: NativeInt):AnsiString; |
function fThueMorse(maxLen: NativeInt):AnsiString; |
||
Line 1,570: | Line 2,164: | ||
fThueMorse(1 shl 30); |
fThueMorse(1 shl 30); |
||
{$IFNDEF LINUX}readln;{$ENDIF} |
{$IFNDEF LINUX}readln;{$ENDIF} |
||
end.</ |
end.</syntaxhighlight> |
||
{{Output}}<pre>Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi |
{{Output}}<pre>Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi |
||
without -O4 -> 2 secs |
without -O4 -> 2 secs |
||
Line 1,587: | Line 2,181: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{works with|Perl|5.x}} |
{{works with|Perl|5.x}} |
||
< |
<syntaxhighlight lang="perl">sub complement |
||
{ |
{ |
||
my $s = shift; |
my $s = shift; |
||
Line 1,602: | Line 2,196: | ||
$str .= complement($str); |
$str .= complement($str); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,615: | Line 2,209: | ||
=={{header|Phix}}== |
=={{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: #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: #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> |
||
Line 1,621: | Line 2,215: | ||
<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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,635: | Line 2,229: | ||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
< |
<syntaxhighlight lang="phixmonti">def inverte |
||
dup len |
dup len |
||
for |
for |
||
Line 1,648: | Line 2,242: | ||
dup print nl nl |
dup print nl nl |
||
inverte chain |
inverte chain |
||
endfor</ |
endfor</syntaxhighlight> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
Line 1,656: | Line 2,250: | ||
(see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence) |
(see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence) |
||
< |
<syntaxhighlight lang="php"><?php |
||
function thueMorseSequence($length) { |
function thueMorseSequence($length) { |
||
Line 1,672: | Line 2,266: | ||
for ($n = 10 ; $n <= 100 ; $n += 10) { |
for ($n = 10 ; $n <= 100 ; $n += 10) { |
||
echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL; |
echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,687: | Line 2,281: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(let R 0 |
||
(prinl R) |
(prinl R) |
||
(for (X 1 (>= 32 X)) |
(for (X 1 (>= 32 X)) |
||
Line 1,696: | Line 2,290: | ||
(bin (x| (dec (** 2 X)) R)) ) ) ) |
(bin (x| (dec (** 2 X)) R)) ) ) ) |
||
(prinl (pack 0 (bin R))) |
(prinl (pack 0 (bin R))) |
||
(inc 'X X) ) )</ |
(inc 'X X) ) )</syntaxhighlight> |
||
=={{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}}== |
=={{header|PowerShell}}== |
||
< |
<syntaxhighlight lang="powershell">function New-ThueMorse ( $Digits ) |
||
{ |
{ |
||
# Start with seed 0 |
# Start with seed 0 |
||
Line 1,729: | Line 2,350: | ||
New-ThueMorse 5 |
New-ThueMorse 5 |
||
New-ThueMorse 16 |
New-ThueMorse 16 |
||
New-ThueMorse 73</ |
New-ThueMorse 73</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>01101 |
<pre>01101 |
||
Line 1,737: | Line 2,358: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="purebasic">EnableExplicit |
||
Procedure.i count_bits(v.i) |
Procedure.i count_bits(v.i) |
||
Line 1,754: | Line 2,375: | ||
Next |
Next |
||
PrintN(~"\n...fin") : Input() |
PrintN(~"\n...fin") : Input() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110 |
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110 |
||
Line 1,761: | Line 2,382: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: By substitution=== |
===Python: By substitution=== |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
m='0' |
m='0' |
||
print(m) |
print(m) |
||
Line 1,771: | Line 2,392: | ||
m=m0+m |
m=m0+m |
||
print(m) |
print(m) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 1,782: | Line 2,403: | ||
===Python: By counting set ones in binary representation=== |
===Python: By counting set ones in binary representation=== |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
>>> def thue_morse_digits(digits): |
>>> def thue_morse_digits(digits): |
||
... return [bin(n).count('1') % 2 for n in range(digits)] |
... return [bin(n).count('1') % 2 for n in range(digits)] |
||
Line 1,790: | Line 2,411: | ||
>>> |
>>> |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]=== |
===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]=== |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
>>> def thue_morse_subs(chars): |
>>> def thue_morse_subs(chars): |
||
... ans = '0' |
... ans = '0' |
||
Line 1,803: | Line 2,424: | ||
'01101001100101101001' |
'01101001100101101001' |
||
>>> |
>>> |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Python: By pair-wise concatenation=== |
===Python: By pair-wise concatenation=== |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
>>> def thue_morse(n): |
>>> def thue_morse(n): |
||
... (v, i) = ('0', '1') |
... (v, i) = ('0', '1') |
||
Line 1,816: | Line 2,437: | ||
'0110100110010110100101100110100110010110011010010110100110010110' |
'0110100110010110100101100110100110010110011010010110100110010110' |
||
>>> |
>>> |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Quackery}}== |
=={{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. |
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 - ^ |
[ i^ dup 1 - ^ |
||
dup 1 >> ^ hex 55555555 & if |
dup 1 >> ^ hex 55555555 & if |
||
Line 1,827: | Line 2,448: | ||
[ digit join ] ] drop ] is thue-morse ( n --> $ ) |
[ digit join ] ] drop ] is thue-morse ( n --> $ ) |
||
20 thue-morse echo$ cr</ |
20 thue-morse echo$ cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,834: | Line 2,455: | ||
=={{header|R}}== |
=={{header|R}}== |
||
< |
<syntaxhighlight lang="rsplus"> |
||
thue_morse <- function(steps) { |
thue_morse <- function(steps) { |
||
sb1 <- "0" |
sb1 <- "0" |
||
Line 1,846: | Line 2,467: | ||
} |
} |
||
cat(thue_morse(6), "\n") |
cat(thue_morse(6), "\n") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,853: | Line 2,474: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0])) |
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0])) |
||
(define (thue-morse-step (s "0")) |
(define (thue-morse-step (s "0")) |
||
Line 1,862: | Line 2,483: | ||
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv))))) |
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv))))) |
||
(for-each displayln (thue-morse 7))</ |
(for-each displayln (thue-morse 7))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 1,876: | Line 2,497: | ||
{{Works with|rakudo|2018.03}} |
{{Works with|rakudo|2018.03}} |
||
First 8 of an infinite sequence |
First 8 of an infinite sequence |
||
<lang |
<syntaxhighlight lang="raku" line>.say for (0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *)[^8];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,888: | Line 2,509: | ||
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 |
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 |
||
^C</pre> |
^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}}== |
=={{header|REXX}}== |
||
===using functions=== |
===using functions=== |
||
Programming note: ''pop count'' (or ''weight'') is the number of <b>1</b>'s bits in the binary representation of a number. |
Programming note: ''pop count'' (or ''weight'') is the number of <b>1</b>'s bits in the binary representation of a number. |
||
< |
<syntaxhighlight 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.*/ |
parse arg N . /*obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/ |
||
Line 1,903: | Line 2,547: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
$pop: return length( space( translate( arg(1), , 0), 0) ) /*count 1's in number.*/ |
$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*/</ |
$weight: return $pop( x2b( d2x( arg(1) ) ) ) /*dec──►bin, pop count*/</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 1,910: | Line 2,554: | ||
===using in-line code=== |
===using in-line code=== |
||
< |
<syntaxhighlight 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.*/ |
parse arg N . /*obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/ |
||
Line 1,917: | Line 2,561: | ||
$= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2 /*append to $.*/ |
$= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2 /*append to $.*/ |
||
end /*j*/ |
end /*j*/ |
||
say $ /*stick a fork in it, we're all done. */</ |
say $ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br> |
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br> |
||
Line 1,924: | Line 2,568: | ||
Because of this, the displaying of the output lacks the granularity of the first two REXX versions. |
Because of this, the displaying of the output lacks the granularity of the first two REXX versions. |
||
< |
<syntaxhighlight 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.*/ |
parse arg N . /*obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N= 6 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N= 6 /*Not specified? Then use the default.*/ |
||
Line 1,931: | Line 2,575: | ||
$= $ || translate($, 10, 01) /*append $'s complement to $ string.*/ |
$= $ || translate($, 10, 01) /*append $'s complement to $ string.*/ |
||
end /*j*/ |
end /*j*/ |
||
say $ /*stick a fork in it, we're all done. */</ |
say $ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 1,938: | Line 2,582: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
tm = "0" |
tm = "0" |
||
see tm |
see tm |
||
Line 1,953: | Line 2,597: | ||
see nl |
see nl |
||
return (previous + tm) |
return (previous + tm) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 1,963: | Line 2,607: | ||
01101001100101101001011001101001 |
01101001100101101001011001101001 |
||
0110100110010110100101100110100110010110011010010110100110010110 |
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> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">puts s = "0" |
||
6.times{puts s << s.tr("01","10")}</ |
6.times{puts s << s.tr("01","10")}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,981: | Line 2,641: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">const ITERATIONS: usize = 8; |
||
fn neg(sequence: &String) -> String { |
fn neg(sequence: &String) -> String { |
||
Line 1,997: | Line 2,657: | ||
sequence = format!("{}{}", sequence, neg(&sequence)); |
sequence = format!("{}{}", sequence, neg(&sequence)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,012: | Line 2,672: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">def thueMorse(n: Int): String = { |
||
val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1")) |
val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1")) |
||
(0 until n).foreach { _ => |
(0 until n).foreach { _ => |
||
Line 2,022: | Line 2,682: | ||
} |
} |
||
(0 to 6).foreach(i => println(s"$i : ${thueMorse(i)}"))</ |
(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)]. |
{{Out}} See it running in your browser by [https://scastie.scala-lang.org/rsF3Y5ABQoK0zZMMA3m6Ow Scastie (JVM)]. |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func recmap(repeat, seed, transform, callback) { |
||
func (repeat, seed) { |
func (repeat, seed) { |
||
callback(seed) |
callback(seed) |
||
Line 2,033: | Line 2,693: | ||
} |
} |
||
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })</ |
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,047: | Line 2,707: | ||
=={{header|SQL}}== |
=={{header|SQL}}== |
||
This example is using SQLite. |
This example is using SQLite. |
||
< |
<syntaxhighlight lang="sql">with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;</syntaxhighlight> |
||
You can add a LIMIT clause to the end to limit how many lines of output you want. |
You can add a LIMIT clause to the end to limit how many lines of output you want. |
||
Line 2,054: | Line 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: |
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: |
||
< |
<syntaxhighlight lang="tcl">proc tm_expand {s} {string map {0 01 1 10} $s} |
||
# this could also be written as: |
# this could also be written as: |
||
# interp alias {} tm_expand {} string map {0 01 1 10} |
# interp alias {} tm_expand {} string map {0 01 1 10} |
||
Line 2,064: | Line 2,724: | ||
} |
} |
||
return $s |
return $s |
||
}</ |
}</syntaxhighlight> |
||
Testing: |
Testing: |
||
< |
<syntaxhighlight lang="tcl">for {set i 0} {$i <= 6} {incr i} { |
||
puts [tm $i] |
puts [tm $i] |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,083: | Line 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: |
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 |
package require sqlite3 ;# available with Tcl8.5+ core |
||
sqlite3 db "" ;# create in-memory database |
sqlite3 db "" ;# create in-memory database |
||
Line 2,089: | Line 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} { |
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 |
puts $a |
||
}</ |
}</syntaxhighlight> |
||
=={{header|uBasic/4tH}}== |
=={{header|uBasic/4tH}}== |
||
<lang>For x = 0 to 6 ' sequence loop |
<syntaxhighlight lang="text">For x = 0 to 6 ' sequence loop |
||
Print Using "_#";x;": "; ' print sequence |
Print Using "_#";x;": "; ' print sequence |
||
For y = 0 To (2^x)-1 ' element loop |
For y = 0 To (2^x)-1 ' element loop |
||
Line 2,109: | Line 2,769: | ||
a@ = SHL(a@, -1) ' shift the number |
a@ = SHL(a@, -1) ' shift the number |
||
Loop |
Loop |
||
Return (b@) ' return number of bits set</ |
Return (b@) ' return number of bits set</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> 0: 0 |
<pre> 0: 0 |
||
Line 2,122: | Line 2,782: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">Option Explicit |
||
Sub Main() |
Sub Main() |
||
Line 2,143: | Line 2,803: | ||
End If |
End If |
||
Thue_Morse = s & k |
Thue_Morse = s & k |
||
End Function</ |
End Function</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>1:=> 0 |
<pre>1:=> 0 |
||
Line 2,156: | Line 2,816: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Imports System.Text |
||
Module Module1 |
Module Module1 |
||
Line 2,175: | Line 2,835: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre> |
||
Line 2,181: | Line 2,841: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="wren">var thueMorse = Fn.new { |n| |
||
var sb0 = "0" |
var sb0 = "0" |
||
var sb1 = "1" |
var sb1 = "1" |
||
Line 2,192: | Line 2,852: | ||
} |
} |
||
for (i in 0..6) System.print("%(i) : %(thueMorse.call(i))")</ |
for (i in 0..6) System.print("%(i) : %(thueMorse.call(i))")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,206: | Line 2,866: | ||
=={{header|XLISP}}== |
=={{header|XLISP}}== |
||
< |
<syntaxhighlight lang="lisp">(defun thue-morse (n) |
||
(defun flip-bits (s) |
(defun flip-bits (s) |
||
(defun flip (l) |
(defun flip (l) |
||
Line 2,228: | Line 2,888: | ||
; test THUE-MORSE by printing the strings it returns for n = 0 to n = 6 |
; 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))</ |
(mapcar (lambda (n) (print (thue-morse n))) (range 0 7))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>"0" |
<pre>"0" |
||
Line 2,239: | Line 2,899: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">string 0; \use zero-terminated strings |
||
char Thue; |
char Thue; |
||
int N, I, J; |
int N, I, J; |
||
Line 2,255: | Line 2,915: | ||
J:= J+I; \set index to terminator |
J:= J+I; \set index to terminator |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,270: | Line 2,930: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="yabasic">tm$ = "0" |
||
for i=1 to 8 |
for i=1 to 8 |
||
? tm$ |
? tm$ |
||
Line 2,283: | Line 2,943: | ||
next |
next |
||
return tm$ |
return tm$ |
||
end sub</ |
end sub</syntaxhighlight> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }</syntaxhighlight> |
||
"12233334444" - "23"-->"14444" |
"12233334444" - "23"-->"14444" |
||
< |
<syntaxhighlight lang="zkl">str:="0"; do(7){ str=nextTM(str.println()) }</syntaxhighlight> |
||
println() returns the result it prints (as a string). |
println() returns the result it prints (as a string). |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="zkl">fcn nextTM2{ |
||
var sb1=Data(Void,"0"), sb2=Data(Void,"1"); |
var sb1=Data(Void,"0"), sb2=Data(Void,"1"); |
||
r:=sb1.text; sb1.append(sb2); sb2.append(r); |
r:=sb1.text; sb1.append(sb2); sb2.append(r); |
||
r |
r |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">do(7){ nextTM2().println() }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 17:08, 16 April 2024
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Create a Thue-Morse sequence.
- See also
- YouTube entry: The Fairest Sharing Sequence Ever
- YouTube entry: Math and OCD - My story with the Thue-Morse sequence
- Task: Fairshare between two and more
11l
F thue_morse_digits(digits)
R (0 .< digits).map(n -> bits:popcount(n) % 2)
print(thue_morse_digits(20))
- Output:
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]
8080 Assembly
The 8080 processor has an internal flag to keep track of the parity of the result of the last operation. This is ideal for generating the Thue-Morse sequence, as one can just count up by incrementing a register, and then check the parity each time. If the parity is even, the corresponding element in the Thue-Morse sequence is 0, if it is odd it is 1. You can even use the same register to iterate over the array where you're storing the elements, and get the parity calculation entirely for free.
Unfortunately, this flag was not deemed very useful otherwise, and in the Z80 support for it was dropped and replaced with a signed overflow flag. This is one of the few places where the Z80 is not backwards compatible with the 8080. This does mean that the binary produced by assembling this program will only run correctly on a real 8080 (or a proper 8080 emulator).
The following program prints the first 256 elements of the Thue-Morse sequence, since that fits neatly in an 8-bit register, but the same principle could be used with a counter of arbitrary size, as after all, XOR is commutative.
org 100h
;;; Write 256 bytes of ASCII '0' starting at address 200h
lxi h,200h ; The array is page-aligned so L starts at 0
mvi a,'0' ; ASCII 0
zero: mov m,a ; Write it to memory at address HL
inr l ; Increment low byte of pointer,
jnz zero ; until it wraps to zero.
;;; Generate the first 256 elements of the Thue-Morse sequence.
gen: jpe $+4 ; If parity is even, skip next instruction
inr m ; (If parity is odd,) increment byte at HL (0->1)
inr l ; Increment low byte of pointer (and set parity),
jnz gen ; Until it wraps again.
;;; Output using CP/M call
inr h ; Increment high byte,
mvi m,'$' ; and write the CP/M string terminator there.
mvi c,9 ; Syscall 9 = print string
lxi d,200h ; The string is at 200h
jmp 5
- Output:
The line breaks are added for clarity, the program does not actually print them.
0110100110010110100101100110100110010110011010010110100110010110 1001011001101001011010011001011001101001100101101001011001101001 1001011001101001011010011001011001101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Action!
PROC Next(CHAR ARRAY s)
BYTE i,len
CHAR c
IF s(0)=0 THEN
s(0)=1 s(1)='0
RETURN
FI
FOR i=1 TO s(0)
DO
IF s(i)='0 THEN
c='1
ELSE
c='0
FI
s(s(0)+i)=c
OD
s(0)==*2
RETURN
PROC Main()
BYTE i
CHAR ARRAY s(256)
s(0)=0
FOR i=0 TO 7
DO
Next(s)
PrintF("T%B=%S%E%E",i,s)
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
T0=0 T1=01 T2=0110 T3=01101001 T4=0110100110010110 T5=01101001100101101001011001101001 T6=0110100110010110100101100110100110010110011010010110100110010110 T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
Ada
Implementation using an L-system.
with Ada.Text_IO; use Ada.Text_IO;
procedure Thue_Morse is
function Replace(S: String) return String is
-- replace every "0" by "01" and every "1" by "10"
(if S'Length = 0 then ""
else (if S(S'First) = '0' then "01" else "10") &
Replace(S(S'First+1 .. S'Last)));
function Sequence (N: Natural) return String is
(if N=0 then "0" else Replace(Sequence(N-1)));
begin
for I in 0 .. 6 loop
Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I));
end loop;
end Thue_Morse;
- Output:
0: 0 1: 01 2: 0110 3: 01101001 4: 0110100110010110 5: 01101001100101101001011001101001 6: 0110100110010110100101100110100110010110011010010110100110010110
ALGOL 68
# "flips" the "bits" in a string (assumed to contain only "0" and "1" characters) #
OP FLIP = ( STRING s )STRING:
BEGIN
STRING result := s;
FOR char pos FROM LWB result TO UPB result DO
result[ char pos ] := IF result[ char pos ] = "0" THEN "1" ELSE "0" FI
OD;
result
END; # FLIP #
# print the first few members of the Thue-Morse sequence #
STRING tm := "0";
TO 7 DO
print( ( tm, newline ) );
tm +:= FLIP tm
OD
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
APL
⍝ generate the first ⍵ elements of the Thue-Morse sequence
tm←{⍵⍴(⊢,~)⍣(⍵≤(⍴⊢))⊢,0}
- Output:
tm 32 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
AppleScript
Functional
------------------------ THUE MORSE ----------------------
-- thueMorse :: Int -> String
on thueMorse(nCycles)
script concatBinaryInverse
on |λ|(xs)
script binaryInverse
on |λ|(x)
1 - x
end |λ|
end script
xs & map(binaryInverse, xs)
end |λ|
end script
intercalate("", ¬
foldl(concatBinaryInverse, [0], ¬
enumFromTo(1, nCycles)))
end thueMorse
--------------------------- TEST -------------------------
on run
thueMorse(6)
--> 0110100110010110100101100110100110010110011010010110100110010110
end run
------------------------- GENERIC ------------------------
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to lstText as text
set my text item delimiters to dlm
return strJoined
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
"0110100110010110100101100110100110010110011010010110100110010110"
Idiomatic
Implements the "flip previous cycles" method, stopping at a specified sequence length.
on ThueMorse(sequenceLength)
if (sequenceLength < 1) then return ""
script o
property sequence : {0}
end script
set counter to 1
set cycleEnd to 1
set i to 1
repeat until (counter = sequenceLength)
set end of o's sequence to ((item i of o's sequence) + 1) mod 2
set counter to counter + 1
if (i < cycleEnd) then
set i to i + 1
else
set i to 1
set cycleEnd to counter
end if
end repeat
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
set sequence to o's sequence as text
set AppleScript's text item delimiters to astid
return sequence
end ThueMorse
return linefeed & ThueMorse(64) & (linefeed & ThueMorse(65))
- Output:
"
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101"
Arturo
thueMorse: function [maxSteps][
result: new []
val: [0]
count: new 0
while [true][
'result ++ join to [:string] val
inc 'count
if count = maxSteps -> return result
val: val ++ map val 'v -> 1 - v
]
return result
]
loop thueMorse 6 'bits ->
print bits
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001
AutoHotkey
ThueMorse(num, iter){
if !iter
return num
for i, n in StrSplit(num)
opp .= !n
res := ThueMorse(num . opp, --iter)
return res
}
Examples:
num := 0
loop 7
output .= A_Index-1 " : " ThueMorse(num, A_Index-1) "`n"
MsgBox % output
- Output:
0 : 0 1 : 01 2 : 0110 3 : 01101001 4 : 0110100110010110 5 : 01101001100101101001011001101001 6 : 0110100110010110100101100110100110010110011010010110100110010110
AWK
BEGIN{print x="0"}
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}
BASIC
BASIC256
tm = "0"
Function Thue_Morse(s)
k = ""
For i = 1 To Length(s)
If Mid(s, i, 1) = "1" Then
k += "0"
Else
k += "1"
End If
Next i
Thue_Morse = s + k
End Function
Print tm
For j = 1 To 7
tm = Thue_Morse(tm)
Print tm
Next j
End
- Output:
Igual que la entrada de FreeBASIC.
Sinclair ZX81 BASIC
10 LET T$="0"
20 PRINT "T0=";T$
30 FOR I=1 TO 7
40 PRINT "T";I;"=";
50 FOR J=1 TO LEN T$
60 IF T$(J)="0" THEN GOTO 90
70 LET T$=T$+"0"
80 GOTO 100
90 LET T$=T$+"1"
100 NEXT J
110 PRINT T$
120 NEXT I
- Output:
T0=0 T1=01 T2=0110 T3=01101001 T4=0110100110010110 T5=01101001100101101001011001101001 T6=0110100110010110100101100110100110010110011010010110100110010110 T7=01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
BBC BASIC
REM >thuemorse
tm$ = "0"
PRINT tm$
FOR i% = 1 TO 8
tm$ = FN_thue_morse(tm$)
PRINT tm$
NEXT
END
:
DEF FN_thue_morse(previous$)
LOCAL i%, tm$
tm$ = ""
FOR i% = 1 TO LEN previous$
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"
NEXT
= previous$ + tm$
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
BCPL
get "libhdr"
let parity(x) =
x=0 -> 0,
(x&1) neqv parity(x>>1)
let start() be
$( for i=0 to 63 do writen(parity(i))
wrch('*N')
$)
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Befunge
This implements the algorithm that counts the 1 bits in the binary representation of the sequence number.
:0\:!v!:\+g20\<>*:*-!#@_
86%2$_:2%02p2/^^82:+1,+*
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
Binary Lambda Calculus
The (infinite) Thue-Morse sequence is output by the 115 bit BLC program
0001000110100001010100011010000000000101101110000101100000010111111101011001111001111110111110000011001011010000010
as documented in https://github.com/tromp/AIT/blob/master/characteristic_sequences/thue-morse.lam
Output:
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101100110100110010110100101100110100101101001...
BQN
TM ← {𝕩↑(⊢∾¬)⍟(1+⌈2⋆⁼𝕩)⥊0}
TM 25 #get first 25 elements
- Output:
⟨ 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 ⟩
C
C: Using string operations
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[]){
char sequence[256+1] = "0";
char inverse[256+1] = "1";
char buffer[256+1];
int i;
for(i = 0; i < 8; i++){
strcpy(buffer, sequence);
strcat(sequence, inverse);
strcat(inverse, buffer);
}
puts(sequence);
return 0;
}
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
C: By counting ones in binary representation of an iterator
#include <stdio.h>
/**
* description : Counts the number of bits set to 1
* input: the number to have its bit counted
* output: the number of bits set to 1
*/
unsigned count_bits(unsigned v) {
unsigned c = 0;
while (v) {
c += v & 1;
v >>= 1;
}
return c;
}
int main(void) {
for (unsigned i = 0; i < 256; ++i) {
putchar('0' + count_bits(i) % 2);
}
putchar('\n');
return 0;
}
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
C: By counting ones in binary representation of an iterator (w/User options)
#include <stdio.h>
/**
* description : Counts the number of bits set to 1
* input: the number to have its bit counted
* output: the number of bits set to 1
*/
unsigned count_bits(unsigned v) {
unsigned c = 0;
while (v) {
c += v & 1;
v >>= 1;
}
return c;
}
int main(void) {
/* i: loop iterator
* length: the length of the sequence to be printed
* ascii_base: the lower char for use when printing
*/
unsigned i, length = 0;
int ascii_base;
/* scan in sequence length */
printf("Sequence length: ");
do {
scanf("%u", &length);
} while (length == 0);
/* scan in sequence mode */
printf("(a)lpha or (b)inary: ");
do {
ascii_base = getchar();
} while ((ascii_base != 'a') && (ascii_base != 'b'));
ascii_base = ascii_base == 'b' ? '0' : 'A';
/* print the Thue-Morse sequence */
for (i = 0; i < length; ++i) {
putchar(ascii_base + count_bits(i) % 2);
}
putchar('\n');
return 0;
}
- Output:
Sequence length: 256 (a)lpha or (b)inary: b 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
C#
using System;
using System.Text;
namespace ThueMorse
{
class Program
{
static void Main(string[] args)
{
Sequence(6);
}
public static void Sequence(int steps)
{
var sb1 = new StringBuilder("0");
var sb2 = new StringBuilder("1");
for (int i = 0; i < steps; i++)
{
var tmp = sb1.ToString();
sb1.Append(sb2);
sb2.Append(tmp);
}
Console.WriteLine(sb1);
Console.ReadLine();
}
}
}
0110100110010110100101100110100110010110011010010110100110010110
C++
#include <iostream>
#include <iterator>
#include <vector>
int main( int argc, char* argv[] ) {
std::vector<bool> t;
t.push_back( 0 );
size_t len = 1;
std::cout << t[0] << "\n";
do {
for( size_t x = 0; x < len; x++ )
t.push_back( t[x] ? 0 : 1 );
std::copy( t.begin(), t.end(), std::ostream_iterator<bool>( std::cout ) );
std::cout << "\n";
len = t.size();
} while( len < 60 );
return 0;
}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
CLU
% Yields an infinite Thue-Morse sequence, digit by digit
tm = iter () yields (char)
n: int := 1
s: string := "0"
while true do
while n <= string$size(s) do
yield(s[n])
n := n + 1
end
s2: array[char] := array[char]$[]
for c: char in string$chars(s) do
if c='0'
then array[char]$addh(s2, '1')
else array[char]$addh(s2, '0')
end
end
s := s || string$ac2s(s2)
end
end tm
% Print the first 64 characters
start_up = proc ()
AMOUNT = 64
po: stream := stream$primary_output()
n: int := 0
for c: char in tm() do
stream$putc(po, c)
n := n + 1
if n = AMOUNT then break end
end
end start_up
- Output:
0110100110010110100101100110100110010110011010010110100110010110
COBOL
IDENTIFICATION DIVISION.
PROGRAM-ID. THUE-MORSE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 STRINGS.
03 CURRENT-STATE PIC X(64).
03 TEMP PIC X(64).
PROCEDURE DIVISION.
BEGIN.
MOVE "0" TO CURRENT-STATE.
PERFORM THUE-MORSE-STEP 8 TIMES.
DISPLAY CURRENT-STATE.
STOP RUN.
THUE-MORSE-STEP.
MOVE CURRENT-STATE TO TEMP.
INSPECT TEMP REPLACING ALL '0' BY 'X'.
INSPECT TEMP REPLACING ALL '1' BY '0'.
INSPECT TEMP REPLACING ALL 'X' BY '1'.
STRING CURRENT-STATE DELIMITED BY SPACE,
TEMP DELIMITED BY SPACE
INTO CURRENT-STATE.
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Common Lisp
(defun bit-complement (bit-vector)
(loop with result = (make-array (length bit-vector) :element-type 'bit)
for b across bit-vector
for i from 0
do (setf (aref result i) (- 1 b))
finally (return result)))
(defun next (bit-vector)
(concatenate 'bit-vector bit-vector (bit-complement bit-vector)))
(defun print-bit-vector (bit-vector)
(loop for b across bit-vector
do (princ b)
finally (terpri)))
(defun thue-morse (max)
(loop repeat (1+ max)
for value = #*0 then (next value)
do (print-bit-vector value)))
(thue-morse 6)
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Cowgol
include "cowgol.coh";
# Find the N'th digit in the Thue-Morse sequence
sub tm(n: uint32): (d: uint8) is
var n2 := n;
while n2 != 0 loop
n2 := n2 >> 1;
n := n ^ n2;
end loop;
d := (n & 1) as uint8;
end sub;
# Print the first 64 digits
var i: uint32 := 0;
while i < 64 loop
print_char('0' + tm(i));
i := i + 1;
end loop;
print_nl();
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Crystal
steps = 6
tmp = ""
s1 = "0"
s2 = "1"
steps.times {
tmp = s1
s1 += s2
s2 += tmp
}
puts s1
- Output:
0110100110010110100101100110100110010110011010010110100110010110
D
import std.range;
import std.stdio;
struct TM {
private char[] sequence = ['0'];
private char[] inverse = ['1'];
private char[] buffer;
enum empty = false;
auto front() {
return sequence;
}
auto popFront() {
buffer = sequence;
sequence ~= inverse;
inverse ~= buffer;
}
}
void main() {
TM sequence;
foreach (step; sequence.take(8)) {
writeln(step);
}
}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Delphi
See Pascal.
Draco
/* Find the N'th digit in the Thue-Morse sequence */
proc nonrec tm(word n) byte:
word n2;
n2 := n;
while n2 ~= 0 do
n2 := n2 >> 1;
n := n >< n2
od;
n & 1
corp
/* Print the first 64 digits */
proc nonrec main() void:
byte i;
for i from 0 upto 63 do
write(tm(i):1)
od
corp
- Output:
0110100110010110100101100110100110010110011010010110100110010110
EasyLang
func$ tmorse s$ .
for i to len s$
if substr s$ i 1 = "1"
k$ &= "0"
else
k$ &= "1"
.
.
return s$ & k$
.
tm$ = "0"
print tm$
for j to 7
tm$ = tmorse tm$
print tm$
.
Elena
ELENA 6.x :
import extensions;
import system'text;
sequence(int steps)
{
var sb1 := TextBuilder.load("0");
var sb2 := TextBuilder.load("1");
for(int i := 0; i < steps; i += 1)
{
var tmp := sb1.Value;
sb1.write(sb2);
sb2.write(tmp)
};
console.printLine(sb1).readLine()
}
public program()
{
sequence(6)
}
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Elixir
Enum.reduce(0..6, '0', fn _,s ->
IO.puts s
s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end)
end)
# or
Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end)
|> Enum.take(7)
|> Enum.each(&IO.puts/1)
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Excel
LAMBDA
Binding the name thueMorse to the following lambda expression in the Name Manager of the Excel WorkBook:
(See LAMBDA: The ultimate Excel worksheet function)
thueMorse
=LAMBDA(n,
APPLYN(n)(
LAMBDA(bits,
APPENDCOLS(bits)(
LAMBDA(x,
IF(0 < x, 0, 1)
)(bits)
)
)
)(0)
)
and also assuming the following generic bindings in the Name Manager for the WorkBook:
APPLYN
=LAMBDA(n,
LAMBDA(f,
LAMBDA(x,
IF(0 < n,
APPLYN(n - 1)(f)(
f(x)
),
x
)
)
)
)
APPENDCOLS
=LAMBDA(xs,
LAMBDA(ys,
LET(
nx, COLUMNS(xs),
colIndexes, SEQUENCE(1, nx + COLUMNS(ys)),
rowIndexes, SEQUENCE(MAX(ROWS(xs), ROWS(ys))),
IFERROR(
IF(nx < colIndexes,
INDEX(ys, rowIndexes, colIndexes - nx),
INDEX(xs, rowIndexes, colIndexes)
),
NA()
)
)
)
)
- Output:
The formula in cell B2 below defines the array of 2^5 = 32 bits which populates the range B2:AG2
fx | =thueMorse(A2) | |||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | AA | AB | AC | AD | AE | AF | AG | ||
1 | Iterations | |||||||||||||||||||||||||||||||||
2 | 5 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Or, as a string, showing up to 2^6 = 64 bits:
fx | =CONCAT(VALUETOTEXT(thueMorse(A2))) | ||
---|---|---|---|
A | B | ||
1 | Iterations | Thue-Morse sequence | |
2 | 0 | 0 | |
3 | 1 | 01 | |
4 | 2 | 0110 | |
5 | 3 | 01101001 | |
6 | 4 | 0110100110010110 | |
7 | 5 | 01101001100101101001011001101001 | |
8 | 6 | 0110100110010110100101100110100110010110011010010110100110010110 |
F#
// Thue-Morse. Nigel Galloway: April 16th., 2024
let rec fG n g=match n with 0->g |1->g+1 |n ->fG(n/2)(g+n&&&1)
let thueMorse=Seq.initInfinite(fun n->(fG n 0)%2)
thueMorse|>Seq.take 25|>Seq.iter(printf "%d "); printfn ""
- Output:
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0
Factor
USING: io kernel math math.parser sequences ;
: thue-morse ( seq n -- seq' )
[ [ ] [ [ 1 bitxor ] map ] bi append ] times ;
: print-tm ( seq -- ) [ number>string ] map "" join print ;
7 <iota> [ { 0 } swap thue-morse print-tm ] each
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Fortran
program thue_morse
implicit none
logical :: f(32) = .false.
integer :: n = 1
do
write(*,*) f(1:n)
if (n > size(f)/2) exit
f(n+1:2*n) = .not. f(1:n)
n = n * 2
end do
end program thue_morse
- Output:
F F T F T T F F T T F T F F T F T T F T F F T T F F T F T T F F T T F T F F T T F F T F T T F T F F T F T T F F T T F T F F T
FreeBASIC
Dim As String tm = "0"
Function Thue_Morse(s As String) As String
Dim As String k = ""
For i As Integer = 1 To Len(s)
If Mid(s, i, 1) = "1" Then
k += "0"
Else
k += "1"
End If
Next i
Thue_Morse = s + k
End Function
Print tm
For j As Integer = 1 To 7
tm = Thue_Morse(tm)
Print tm
Next j
End
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
FutureBasic
local fn ThueMorse( s as Str255 ) as Str255
Str255 k
short i
k = ""
for i = 1 to len$(s)
if mid$(s, i, 1) == "1"
k += "0"
else
k += "1"
end if
next
end fn = s + k
local fn DoIt
Str255 tm
short i
tm = "0"
print tm
for i = 1 to 7
tm = fn ThueMorse( tm )
print tm
next
end fn
fn DoIt
HandleEvents
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution 1
Solution 2
Solution 3
Solution 4
Notice that this solution generates a string.
Solution 5
Notice that this solution generates a string.
Solution 6
Notice that this solution generates a string.
Solution 7. L-system
There are generic functions written in Fōrmulæ to compute an L-system in the page L-system.
The program that creates a Hilbert curve is:
Go
// prints the first few members of the Thue-Morse sequence
package main
import (
"fmt"
"bytes"
)
// sets tmBuffer to the next member of the Thue-Morse sequence
// tmBuffer must contain a valid Thue-Morse sequence member before the call
func nextTMSequenceMember( tmBuffer * bytes.Buffer ) {
// "flip" the bytes, adding them to the buffer
for b, currLength, currBytes := 0, tmBuffer.Len(), tmBuffer.Bytes() ; b < currLength; b ++ {
if currBytes[ b ] == '1' {
tmBuffer.WriteByte( '0' )
} else {
tmBuffer.WriteByte( '1' )
}
}
}
func main() {
var tmBuffer bytes.Buffer
// initial sequence member is "0"
tmBuffer.WriteByte( '0' )
fmt.Println( tmBuffer.String() )
for i := 2; i <= 7; i ++ {
nextTMSequenceMember( & tmBuffer )
fmt.Println( tmBuffer.String() )
}
}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Haskell
Computing progressively longer prefixes of the sequence:
thueMorsePxs :: [[Int]]
thueMorsePxs = iterate ((++) <*> map (1 -)) [0]
{-
= Control.Monad.ap (++) (map (1-)) `iterate` [0]
= iterate (\ xs -> (++) xs (map (1-) xs)) [0]
= iterate (\ xs -> xs ++ map (1-) xs) [0]
-}
main :: IO ()
main = print $ thueMorsePxs !! 5
- Output:
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]
The infinite sequence itself:
thueMorse :: [Int]
thueMorse = 0 : g 1
where
g i = (1 -) <$> take i thueMorse <> g (2 * i)
main :: IO ()
main = print $ take 33 thueMorse
- Output:
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1]
J
We only show a prefix of the sequence:
(, -.)@]^:[&0]9
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...
Or, more compactly:
' '-.~":(, -.)@]^:[&0]9
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...
Java
public class ThueMorse {
public static void main(String[] args) {
sequence(6);
}
public static void sequence(int steps) {
StringBuilder sb1 = new StringBuilder("0");
StringBuilder sb2 = new StringBuilder("1");
for (int i = 0; i < steps; i++) {
String tmp = sb1.toString();
sb1.append(sb2);
sb2.append(tmp);
}
System.out.println(sb1);
}
}
0110100110010110100101100110100110010110011010010110100110010110
JavaScript
ES5
(function(steps) {
'use strict';
var i, tmp, s1 = '0', s2 = '1';
for (i = 0; i < steps; i++) {
tmp = s1;
s1 += s2;
s2 += tmp;
}
console.log(s1);
})(6);
0110100110010110100101100110100110010110011010010110100110010110
ES6
(() => {
'use strict';
// thueMorsePrefixes :: () -> [[Int]]
const thueMorsePrefixes = () =>
iterate(
ap(append)(
map(x => 1 - x)
)
)([0]);
// ----------------------- TEST -----------------------
const main = () =>
// Fifth iteration.
// 2 ^ 5 = 32 terms of the Thue-Morse sequence.
showList(
index(thueMorsePrefixes())(
5
)
);
// ---------------- GENERIC FUNCTIONS -----------------
// ap :: (a -> b -> c) -> (a -> b) -> a -> c
const ap = f =>
// Applicative instance for functions.
// f(x) applied to g(x).
g => x => f(x)(
g(x)
);
// append (++) :: [a] -> [a] -> [a]
// append (++) :: String -> String -> String
const append = xs =>
// A list or string composed by
// the concatenation of two others.
ys => xs.concat(ys);
// index (!!) :: Generator (Int, a) -> Int -> Maybe a
const index = xs =>
i => (take(i)(xs), xs.next().value);
// iterate :: (a -> a) -> a -> Gen [a]
const iterate = f =>
function*(x) {
let v = x;
while (true) {
yield(v);
v = f(v);
}
};
// map :: (a -> b) -> [a] -> [b]
const map = f =>
// The list obtained by applying f
// to each element of xs.
// (The image of xs under f).
xs => xs.map(f);
// showList :: [a] -> String
const showList = xs =>
'[' + xs.map(x => x.toString())
.join(',')
.replace(/[\"]/g, '') + ']';
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// MAIN ---
return main();
})();
- Output:
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]
jq
Works with gojq, the Go implementation of jq
`thueMorse` as defined here generates an indefinitely long stream of the Thue-Morse integers:
def thueMorse:
0,
({sb0: "0", sb1: "1", n:1 }
| while( true;
{n: (.sb0|length),
sb0: (.sb0 + .sb1),
sb1: (.sb1 + .sb0)} )
| .sb0[.n:]
| explode[]
| . - 48);
Example:
[limit(100;thueMorse)] | join("")
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110
Julia
function thuemorse(len::Int)
rst = Vector{Int8}(len)
rst[1] = 0
i, imax = 2, 1
while i ≤ len
while i ≤ len && i ≤ 2 * imax
rst[i] = 1 - rst[i-imax]
i += 1
end
imax *= 2
end
return rst
end
println(join(thuemorse(100)))
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110
Kotlin
Kotlin: From java
The original Java code, as translated to Kotlin, with a few cleanups.
fun thueMorse(n: Int): String {
val sb0 = StringBuilder("0")
val sb1 = StringBuilder("1")
repeat(n) {
val tmp = sb0.toString()
sb0.append(sb1)
sb1.append(tmp)
}
return sb0.toString()
}
fun main() {
for (i in 0..6) println("$i : ${thueMorse(i)}")
}
- Output:
0 : 0 1 : 01 2 : 0110 3 : 01101001 4 : 0110100110010110 5 : 01101001100101101001011001101001 6 : 0110100110010110100101100110100110010110011010010110100110010110
Kotlin: Alternative
Same general idea as above, but using a few Kotlin specific code shortcuts.
fun thueMorse(n: Int): String {
val pair = "0" to "1"
repeat(n) { pair = with(pair) { first + second to second + first } }
return pair.first
}
fun main() {
for (i in 0..6) println("$i : ${thueMorse(i)}")
}
- Output:
0 : 0 1 : 01 2 : 0110 3 : 01101001 4 : 0110100110010110 5 : 01101001100101101001011001101001 6 : 0110100110010110100101100110100110010110011010010110100110010110
Lambdatalk
{def thue_morse
{def thue_morse.r
{lambda {:steps :s1 :s2 :i}
{if {> :i :steps}
then :s1
else {thue_morse.r :steps :s1:s2 :s2:s1 {+ :i 1}}}}}
{lambda {:steps}
{thue_morse.r :steps 0 1 1}}}
-> thue_morse
{thue_morse 6}
-> 0110100110010110100101100110100110010110011010010110100110010110
Lua
ThueMorse = {sequence = "0"}
function ThueMorse:show ()
print(self.sequence)
end
function ThueMorse:addBlock ()
local newBlock = ""
for bit = 1, self.sequence:len() do
if self.sequence:sub(bit, bit) == "1" then
newBlock = newBlock .. "0"
else
newBlock = newBlock .. "1"
end
end
self.sequence = self.sequence .. newBlock
end
for i = 1, 5 do
ThueMorse:show()
ThueMorse:addBlock()
end
- Output:
0 01 0110 01101001 0110100110010110
M2000 Interpreter
Adapted from Java.
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).
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$
- Output:
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
All together
// 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$
- Output:
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
MACRO-11
.TITLE THUE
.MCALL .TTYOUT,.EXIT
THUE:: MOV #100,R3 ; 64 ITEMS
CLR R2
1$: JSR PC,SEQ ; GET THUE-MORSE SEQUENCE ITEM
ADD #60,R0 ; MAKE ASCII
.TTYOUT ; PRINT
INC R2
SOB R3,1$
.EXIT
; LET R0 = R2'TH ITEM IN THUE MORSE SEQUENCE
SEQ: CLR R0
MOV #20,R1
1$: ROR R0
XOR R2,R0
SOB R1,1$
BIC #^C1,R0
RTS PC
.END THUE
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Mathematica/Wolfram Language
ThueMorse[Range[20]]
- Output:
{1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0}
MATLAB
MATLAB: By counting set ones in binary representation
tmSequence = thue_morse_digits(20);
disp(tmSequence);
function tmSequence = thue_morse_digits(n)
tmSequence = zeros(1, n);
for i = 0:(n-1)
binStr = dec2bin(i);
numOnes = sum(binStr == '1');
tmSequence(i+1) = mod(numOnes, 2);
end
end
- Output:
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
Miranda
main :: [sys_message]
main = [Stdout (show (take 30 thue) ++ "\n")]
thue :: [num]
thue = 0 : 1 : concat [[x, 1-x] | x<-tl thue]
- Output:
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
Modula-2
MODULE ThueMorse;
FROM Strings IMPORT Concat;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
PROCEDURE Sequence(steps : CARDINAL);
TYPE String = ARRAY[0..128] OF CHAR;
VAR sb1,sb2,tmp : String;
i : CARDINAL;
BEGIN
sb1 := "0";
sb2 := "1";
WHILE i<steps DO
tmp := sb1;
Concat(sb1, sb2, sb1);
Concat(sb2, tmp, sb2);
INC(i);
END;
WriteString(sb1);
WriteLn;
END Sequence;
BEGIN
Sequence(6);
ReadChar;
END ThueMorse.
NewLISP
(define (Thue-Morse loops)
(setf TM '(0))
(println TM)
(for (i 1 (-- loops))
(setf tmp TM)
(replace '0 tmp '_)
(replace '1 tmp '0)
(replace '_ tmp '1)
(setf TM (append TM tmp))
(println TM)
)
)
(Thue-Morse 5)
(exit)
- Output:
(0) (0 1) (0 1 1 0) (0 1 1 0 1 0 0 1) (0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0)
Nim
Using an iterator and sequences concatenations
import sequtils, strutils
iterator thueMorse(maxSteps = int.high): string =
var val = @[0]
var count = 0
while true:
yield val.join()
inc count
if count == maxSteps: break
val &= val.mapIt(1 - it)
for bits in thueMorse(6):
echo bits
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001
Using fast sequence generation algorithm from Wikipedia
type Bit = 0..1
proc thueMorse(seqLength: Positive): string =
var val = Bit(0)
for n in 0..<seqLength:
let x = n xor (n - 1)
if ((x xor x shr 1) and 0x55555555) != 0:
val = 1 - val
result.add chr(val + ord('0'))
echo thueMorse(64)
- Output:
0110100110010110100101100110100110010110011010010110100110010110
OASYS Assembler
; Thue-Morse sequence
[*'A] ; Ensure the vocabulary is not empty
[&] ; Declare the initialization procedure
%#1> ; Initialize length counter
%@*> ; Create first object
,#1> ; Initialize loop counter
: ; Begin loop
%@<.#<PI ; Print current cell
*.#%@<.#<NOT> ; Create new cell
%@%@<NXT> ; Advance to next cell
,#,#<DN> ; Decrement loop counter
,#</ ; Check if loop counter is now zero
%#%#<2MUL> ; Double length counter
,#%#<> ; Reset loop counter
%@FO> ; Reset object pointer
CR ; Line break
| ; Repeat loop
The standard DOS-based interpreter will display an error message about word too long after 7 lines are output; this is because the 8th line does not fit in 80 columns.
Objeck
class ThueMorse {
function : Main(args : String[]) ~ Nil {
Sequence(6);
}
function : Sequence(steps : Int) ~ Nil {
sb1 := "0";
sb2 := "1";
for(i := 0; i < steps; i++;) {
tmp := String->New(sb1);
sb1 += sb2;
sb2 += tmp;
};
sb1->PrintLine();
}
}
Output:
0110100110010110100101100110100110010110011010010110100110010110
OCaml
By counting ones in binary representation of an iterator
(* description: Counts the number of bits set to 1
input: the number to have its bit counted
output: the number of bits set to 1 *)
let count_bits v =
let rec aux c v =
if v <= 0 then c
else aux (c + (v land 1)) (v lsr 1)
in
aux 0 v
let () =
for i = 0 to pred 256 do
print_char (
match (count_bits i) mod 2 with
| 0 -> '0'
| 1 -> '1'
| _ -> assert false)
done;
print_newline ()
Using string operations
let sequence steps =
let sb1 = Buffer.create 100 in
let sb2 = Buffer.create 100 in
Buffer.add_char sb1 '0';
Buffer.add_char sb2 '1';
for i = 0 to pred steps do
let tmp = Buffer.contents sb1 in
Buffer.add_string sb1 (Buffer.contents sb2);
Buffer.add_string sb2 tmp;
done;
(Buffer.contents sb1)
let () =
print_endline (sequence 6);
Pascal
Like the C++ Version [[1]] the lenght of the sequence is given in advance.
Program ThueMorse;
function fThueMorse(maxLen: NativeInt):AnsiString;
//double by appending the flipped original 0 -> 1;1 -> 0
//Flipping between two values:x oszillating A,B,A,B -> x_next = A+B-x
//Beware A+B < High(Char), the compiler will complain ...
const
cVal0 = '^';cVal1 = 'v';// cVal0 = '0';cVal1 = '1';
var
pOrg,
pRpl : pansiChar;
i,k,ml : NativeUInt;//MaxLen: NativeInt
Begin
iF maxlen < 1 then
Begin
result := '';
EXIT;
end;
//setlength only one time
setlength(result,Maxlen);
pOrg := @result[1];
pOrg[0] := cVal0;
IF maxlen = 1 then
EXIT;
pRpl := pOrg;
inc(pRpl);
k := 1;
ml:= Maxlen;
repeat
i := 0;
repeat
pRpl[0] := ansichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
inc(pRpl);
inc(i);
until i>=k;
inc(k,k);
until k+k> ml;
// the rest
i := 0;
k := ml-k;
IF k > 0 then
repeat
pRpl[0] := ansichar(Ord(cVal0)+Ord(cVal1)-Ord(pOrg[i]));
inc(pRpl);
inc(i)
until i>=k;
end;
var
i : integer;
Begin
For i := 0 to 8 do
writeln(i:3,' ',fThueMorse(i));
fThueMorse(1 shl 30);
{$IFNDEF LINUX}readln;{$ENDIF}
end.
- Output:
Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphiwithout -O4 -> 2 secs
0 1 ^ 2 ^v 3 ^vv 4 ^vv^ 5 ^vv^v 6 ^vv^v^ 7 ^vv^v^^ 8 ^vv^v^^vnot written: 1 shl 30 == 1GB
real 0m0.806s user 0m0.563s sys 0m0.242s
Perl
sub complement
{
my $s = shift;
$s =~ tr/01/10/;
return $s;
}
my $str = '0';
for (0..6) {
say $str;
$str .= complement($str);
}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Phix
string tm = "0" for i=1 to 8 do printf(1,"%s\n",tm) tm &= sq_sub('0'+'1',tm) end for
- Output:
"0" "01" "0110" "01101001" "0110100110010110" "01101001100101101001011001101001" "0110100110010110100101100110100110010110011010010110100110010110" "01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001"
Phixmonti
def inverte
dup len
for
var i
i get not i set
endfor
enddef
0 1 tolist
8 for
.
dup print nl nl
inverte chain
endfor
PHP
Fast sequence generation - This implements the algorithm that find the highest-order bit in the binary representation of n that is different from the same bit in the representation of n − 1 (see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence)
<?php
function thueMorseSequence($length) {
$sequence = '';
for ($digit = $n = 0 ; $n < $length ; $n++) {
$x = $n ^ ($n - 1);
if (($x ^ ($x >> 1)) & 0x55555555) {
$digit = 1 - $digit;
}
$sequence .= $digit;
}
return $sequence;
}
for ($n = 10 ; $n <= 100 ; $n += 10) {
echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL;
}
- Output:
10 : 0110100110 20 : 01101001100101101001 30 : 011010011001011010010110011010 40 : 0110100110010110100101100110100110010110 50 : 01101001100101101001011001101001100101100110100101 60 : 011010011001011010010110011010011001011001101001011010011001 70 : 0110100110010110100101100110100110010110011010010110100110010110100101 80 : 01101001100101101001011001101001100101100110100101101001100101101001011001101001 90 : 011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110 100 : 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110
PicoLisp
(let R 0
(prinl R)
(for (X 1 (>= 32 X))
(setq R
(bin
(pack
(bin R)
(bin (x| (dec (** 2 X)) R)) ) ) )
(prinl (pack 0 (bin R)))
(inc 'X X) ) )
PL/M
100H:
BDOS: PROCEDURE (F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PUT$CHAR: PROCEDURE (C); DECLARE C BYTE; CALL BDOS(2,C); END PUT$CHAR;
/* FIND THE NTH ELEMENT OF THE THUE-MORSE SEQUENCE */
THUE: PROCEDURE (N) BYTE;
DECLARE N ADDRESS;
N = N XOR SHR(N,8);
N = N XOR SHR(N,4);
N = N XOR SHR(N,2);
N = N XOR SHR(N,1);
RETURN N AND 1;
END THUE;
/* PRINT THE FIRST 64 ELEMENTS */
DECLARE I BYTE;
DO I=0 TO 63;
CALL PUT$CHAR('0' + THUE(I));
END;
CALL EXIT;
EOF
- Output:
0110100110010110100101100110100110010110011010010110100110010110
PowerShell
function New-ThueMorse ( $Digits )
{
# Start with seed 0
$ThueMorse = "0"
# Decrement digits remaining
$Digits--
# While we still have digits to calculate...
While ( $Digits -gt 0 )
{
# Number of digits we'll get this loop (what we still need up to the maximum available), corrected to 0 base
$LastDigit = [math]::Min( $ThueMorse.Length, $Digits ) - 1
# Loop through each digit
ForEach ( $i in 0..$LastDigit )
{
# Append the twos complement
$ThueMorse += ( 1 - $ThueMorse.Substring( $i, 1 ) )
}
# Calculate the number of digits still remaining
$Digits = $Digits - $LastDigit - 1
}
return $ThueMorse
}
New-ThueMorse 5
New-ThueMorse 16
New-ThueMorse 73
- Output:
01101 0110100110010110 0110100110010110100101100110100110010110011010010110100110010110100101100
PureBasic
EnableExplicit
Procedure.i count_bits(v.i)
Define c.i
While v
c+v&1
v>>1
Wend
ProcedureReturn c
EndProcedure
If OpenConsole()
Define n.i
For n=0 To 255
Print(Str(count_bits(n)%2))
Next
PrintN(~"\n...fin") : Input()
EndIf
- Output:
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110 ...fin
Python
Python: By substitution
m='0'
print(m)
for i in range(0,6):
m0=m
m=m.replace('0','a')
m=m.replace('1','0')
m=m.replace('a','1')
m=m0+m
print(m)
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Python: By counting set ones in binary representation
>>> def thue_morse_digits(digits):
... return [bin(n).count('1') % 2 for n in range(digits)]
...
>>> thue_morse_digits(20)
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]
>>>
Python: By substitution system
>>> def thue_morse_subs(chars):
... ans = '0'
... while len(ans) < chars:
... ans = ans.replace('0', '0_').replace('1', '10').replace('_', '1')
... return ans[:chars]
...
>>> thue_morse_subs(20)
'01101001100101101001'
>>>
Python: By pair-wise concatenation
>>> def thue_morse(n):
... (v, i) = ('0', '1')
... for _ in range(0,n):
... (v, i) = (v + i, i + v)
... return v
...
>>> thue_morse(6)
'0110100110010110100101100110100110010110011010010110100110010110'
>>>
Quackery
This uses the fast sequence generation algorithm from the wiki article.
[ [] 0 rot times
[ i^ dup 1 - ^
dup 1 >> ^ hex 55555555 & if
[ 1 swap - ]
dup dip
[ digit join ] ] drop ] is thue-morse ( n --> $ )
20 thue-morse echo$ cr
- Output:
01101001100101101001
R
thue_morse <- function(steps) {
sb1 <- "0"
sb2 <- "1"
for (idx in 1:steps) {
tmp <- sb1
sb1 <- paste0(sb1, sb2)
sb2 <- paste0(sb2, tmp)
}
sb1
}
cat(thue_morse(6), "\n")
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Racket
#lang racket
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))
(define (thue-morse-step (s "0"))
(string-append s (list->string (map 1<->0 (string->list s)))))
(define (thue-morse n)
(let inr ((n (max (sub1 n) 0)) (rv (list "0")))
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))
(for-each displayln (thue-morse 7))
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Raku
(formerly Perl 6)
First 8 of an infinite sequence
.say for (0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *)[^8];
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001 ^C
Refal
$ENTRY Go {
= <Prout <ThueMorse 7>>
};
ThueMorse {
0 e.X = e.X;
s.N e.X = <ThueMorse <- s.N 1> <ThueMorseStep e.X>>;
};
ThueMorseStep {
= '0';
e.X = e.X <Invert e.X>;
};
Invert {
= ;
'0' e.X = '1' <Invert e.X>;
'1' e.X = '0' <Invert e.X>;
};
- Output:
0110100110010110100101100110100110010110011010010110100110010110
REXX
using functions
Programming note: pop count (or weight) is the number of 1's bits in the binary representation of a number.
/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/
$= /*the Thue─Morse sequence (so far). */
do j=0 to N /*generate sequence up to the Nth item.*/
$= $ || $weight(j) // 2 /*append the item to the Thue─Morse seq*/
end /*j*/
say $
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
$pop: return length( space( translate( arg(1), , 0), 0) ) /*count 1's in number.*/
$weight: return $pop( x2b( d2x( arg(1) ) ) ) /*dec──►bin, pop count*/
- output when using the default input:
01101001100101101001011001101001100101100110100101101001100101101001011001101001
using in-line code
/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/
$= /*the Thue─Morse sequence (so far). */
do j=0 to N /*generate sequence up to the Nth item.*/
$= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2 /*append to $.*/
end /*j*/
say $ /*stick a fork in it, we're all done. */
- output is identical to the 1st REXX version.
using 2's complement
Programming note: this method displays the sequence, but it doubles in (binary) length each iteration.
Because of this, the displaying of the output lacks the granularity of the first two REXX versions.
/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 6 /*Not specified? Then use the default.*/
$= 0 /*the Thue─Morse sequence (so far). */
do j=1 for N /*generate sequence up to the Nth item.*/
$= $ || translate($, 10, 01) /*append $'s complement to $ string.*/
end /*j*/
say $ /*stick a fork in it, we're all done. */
- output when using the default input:
0110100110010110100101100110100110010110011010010110100110010110
Ring
tm = "0"
see tm
for n = 1 to 6
tm = thue_morse(tm)
see tm
next
func thue_morse(previous)
tm = ""
for i = 1 to len(previous)
if (substr(previous, i, 1) = "1") tm = tm + "0" else tm = tm + "1" ok
next
see nl
return (previous + tm)
Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
RPL
We use here the bitwise negation method: it needs few words and is actually faster than the "fast" generation method, because RPL is better in list handling than in bitwise calculations.
≪ { 0 }
WHILE DUP2 SIZE > REPEAT
1 OVER - +
END
1 ROT SUB
≫ 'THUEM' STO
20 THUEM
- Output:
1: { 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 }
Ruby
puts s = "0"
6.times{puts s << s.tr("01","10")}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Rust
const ITERATIONS: usize = 8;
fn neg(sequence: &String) -> String {
sequence.chars()
.map(|ch| {
(1 - ch.to_digit(2).unwrap()).to_string()
})
.collect::<String>()
}
fn main() {
let mut sequence: String = String::from("0");
for i in 0..ITERATIONS {
println!("{}: {}", i + 1, sequence);
sequence = format!("{}{}", sequence, neg(&sequence));
}
}
- Output:
1: 0 2: 01 3: 0110 4: 01101001 5: 0110100110010110 6: 01101001100101101001011001101001 7: 0110100110010110100101100110100110010110011010010110100110010110 8: 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
Scala
def thueMorse(n: Int): String = {
val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1"))
(0 until n).foreach { _ =>
val tmp = sb0.toString()
sb0.append(sb1)
sb1.append(tmp)
}
sb0.toString()
}
(0 to 6).foreach(i => println(s"$i : ${thueMorse(i)}"))
- Output:
See it running in your browser by Scastie (JVM).
Sidef
func recmap(repeat, seed, transform, callback) {
func (repeat, seed) {
callback(seed)
repeat > 0 && __FUNC__(repeat-1, transform(seed))
}(repeat, seed)
}
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
SQL
This example is using SQLite.
with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;
You can add a LIMIT clause to the end to limit how many lines of output you want.
Tcl
Since string map correctly handles overlapping replacements, the simple map 0 -> 01; 1 -> 10 can be applied with no special handling:
proc tm_expand {s} {string map {0 01 1 10} $s}
# this could also be written as:
# interp alias {} tm_expand {} string map {0 01 1 10}
proc tm {k} {
set s 0
while {[incr k -1] >= 0} {
set s [tm_expand $s]
}
return $s
}
Testing:
for {set i 0} {$i <= 6} {incr i} {
puts [tm $i]
}
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
For giggles, also note that the above SQL solution can be "natively" applied in Tcl8.5+, which bundles Sqlite as a core extension:
package require sqlite3 ;# available with Tcl8.5+ core
sqlite3 db "" ;# create in-memory database
set LIMIT 6
db eval {with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select a from a limit $LIMIT} {
puts $a
}
uBasic/4tH
For x = 0 to 6 ' sequence loop
Print Using "_#";x;": "; ' print sequence
For y = 0 To (2^x)-1 ' element loop
Print AND(FUNC(_Parity(y)),1); ' print element
Next ' next element
Print ' terminate elements line
Next ' next sequence
End
_Parity Param (1) ' parity function
Local (1) ' number of bits set
b@ = 0 ' no bits set yet
Do While a@ # 0 ' until all bits are counted
If AND (a@, 1) Then b@ = b@ + 1 ' bit set? increment count
a@ = SHL(a@, -1) ' shift the number
Loop
Return (b@) ' return number of bits set
- Output:
0: 0 1: 01 2: 0110 3: 01101001 4: 0110100110010110 5: 01101001100101101001011001101001 6: 0110100110010110100101100110100110010110011010010110100110010110 0 OK, 0:123
VBA
Option Explicit
Sub Main()
Dim i&, t$
For i = 1 To 8
t = Thue_Morse(t)
Debug.Print i & ":=> " & t
Next
End Sub
Private Function Thue_Morse(s As String) As String
Dim k$
If s = "" Then
k = "0"
Else
k = s
k = Replace(k, "1", "2")
k = Replace(k, "0", "1")
k = Replace(k, "2", "0")
End If
Thue_Morse = s & k
End Function
- Output:
1:=> 0 2:=> 01 3:=> 0110 4:=> 01101001 5:=> 0110100110010110 6:=> 01101001100101101001011001101001 7:=> 0110100110010110100101100110100110010110011010010110100110010110 8:=> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
Visual Basic .NET
Imports System.Text
Module Module1
Sub Sequence(steps As Integer)
Dim sb1 As New StringBuilder("0")
Dim sb2 As New StringBuilder("1")
For index = 1 To steps
Dim tmp = sb1.ToString
sb1.Append(sb2)
sb2.Append(tmp)
Next
Console.WriteLine(sb1)
End Sub
Sub Main()
Sequence(6)
End Sub
End Module
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Wren
var thueMorse = Fn.new { |n|
var sb0 = "0"
var sb1 = "1"
(0...n).each { |i|
var tmp = sb0
sb0 = sb0 + sb1
sb1 = sb1 + tmp
}
return sb0
}
for (i in 0..6) System.print("%(i) : %(thueMorse.call(i))")
- Output:
0 : 0 1 : 01 2 : 0110 3 : 01101001 4 : 0110100110010110 5 : 01101001100101101001011001101001 6 : 0110100110010110100101100110100110010110011010010110100110010110
XLISP
(defun thue-morse (n)
(defun flip-bits (s)
(defun flip (l)
(if (not (null l))
(cons
(if (equal (car l) #\1)
#\0
#\1)
(flip (cdr l)))))
(list->string (flip (string->list s))))
(if (= n 0)
"0"
(string-append (thue-morse (- n 1)) (flip-bits (thue-morse (- n 1))))))
; define RANGE, for testing purposes
(defun range (x y)
(if (< x y)
(cons x (range (+ x 1) y))))
; test THUE-MORSE by printing the strings it returns for n = 0 to n = 6
(mapcar (lambda (n) (print (thue-morse n))) (range 0 7))
- Output:
"0" "01" "0110" "01101001" "0110100110010110" "01101001100101101001011001101001" "0110100110010110100101100110100110010110011010010110100110010110"
XPL0
string 0; \use zero-terminated strings
char Thue;
int N, I, J;
[Thue:= Reserve(Free); \reserve all available memory
Thue(0):= ^0;
J:= 1; \set index to terminator
for N:= 0 to 6 do
[Thue(J):= 0; \terminate string
Text(0, Thue); \show result
CrLf(0);
I:= 0; \invert string and store it on the end
repeat Thue(J+I):= Thue(I) xor 1;
I:= I+1;
until I = J;
J:= J+I; \set index to terminator
];
]
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Yabasic
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
zkl
fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }
"12233334444" - "23"-->"14444"
str:="0"; do(7){ str=nextTM(str.println()) }
println() returns the result it prints (as a string).
fcn nextTM2{
var sb1=Data(Void,"0"), sb2=Data(Void,"1");
r:=sb1.text; sb1.append(sb2); sb2.append(r);
r
}
do(7){ nextTM2().println() }
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
- Programming Tasks
- Solutions by Programming Task
- 11l
- 8080 Assembly
- Action!
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- Sinclair ZX81 BASIC
- BBC BASIC
- BCPL
- Befunge
- Binary Lambda Calculus
- BQN
- C
- C sharp
- C++
- CLU
- COBOL
- Common Lisp
- Cowgol
- Crystal
- D
- Delphi
- Draco
- EasyLang
- Elena
- Elixir
- Excel
- F Sharp
- Factor
- Fortran
- FreeBASIC
- FutureBasic
- Fōrmulæ
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lambdatalk
- Lua
- M2000 Interpreter
- MACRO-11
- Mathematica
- Wolfram Language
- MATLAB
- Miranda
- Modula-2
- NewLISP
- Nim
- OASYS Assembler
- Objeck
- OCaml
- Pascal
- Perl
- Phix
- Phixmonti
- PHP
- PicoLisp
- PL/M
- PowerShell
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- Refal
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Sidef
- SQL
- Tcl
- UBasic/4tH
- VBA
- Visual Basic .NET
- Wren
- XLISP
- XPL0
- Yabasic
- Zkl