Jump to content

Thue-Morse: Difference between revisions

Thue-Morse (view source)

Revision as of 18:41, 28 August 2022

2,890 bytes added ,  1 year ago
m
syntax highlighting fixup automation
(Add CLU)
m (syntax highlighting fixup automation)
Line 14:
{{trans|Python: By counting set ones in binary representation}}
 
<langsyntaxhighlight lang="11l">F thue_morse_digits(digits)
R (0 .< digits).map(n -> bin(n).count(‘1’) % 2)
 
print(thue_morse_digits(20))</langsyntaxhighlight>
 
{{out}}
Line 41:
after all, XOR is commutative.
 
<langsyntaxhighlight lang="8080asm"> org 100h
;;; Write 256 bytes of ASCII '0' starting at address 200h
lxi h,200h ; The array is page-aligned so L starts at 0
Line 58:
mvi c,9 ; Syscall 9 = print string
lxi d,200h ; The string is at 200h
jmp 5</langsyntaxhighlight>
 
{{out}}
Line 70:
 
=={{header|Action!}}==
<langsyntaxhighlight Actionlang="action!">PROC Next(CHAR ARRAY s)
BYTE i,len
CHAR c
Line 101:
PrintF("T%B=%S%E%E",i,s)
OD
RETURN</langsyntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Thue-Morse.png Screenshot from Atari 8-bit computer]
Line 125:
Implementation using an L-system.
 
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO; use Ada.Text_IO;
 
procedure Thue_Morse is
Line 142:
Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I));
end loop;
end Thue_Morse;</langsyntaxhighlight>
 
{{out}}
Line 154:
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68"># "flips" the "bits" in a string (assumed to contain only "0" and "1" characters) #
OP FLIP = ( STRING s )STRING:
BEGIN
Line 169:
print( ( tm, newline ) );
tm +:= FLIP tm
OD</langsyntaxhighlight>
{{out}}
<pre>
Line 186:
{{Trans|JavaScript}}
 
<langsyntaxhighlight AppleScriptlang="applescript">------------------------ THUE MORSE ----------------------
 
-- thueMorse :: Int -> String
Line 278:
end script
end if
end mReturn</langsyntaxhighlight>
<pre>"0110100110010110100101100110100110010110011010010110100110010110"</pre>
----
Line 286:
Implements the "flip previous cycles" method, stopping at a specified sequence length.
 
<langsyntaxhighlight lang="applescript">on ThueMorse(sequenceLength)
if (sequenceLength < 1) then return ""
Line 315:
end ThueMorse
 
return linefeed & ThueMorse(64) & (linefeed & ThueMorse(65))</langsyntaxhighlight>
 
{{output}}
<langsyntaxhighlight lang="applescript">"
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101"</langsyntaxhighlight>
 
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">thueMorse: function [maxSteps][
result: new []
val: [0]
Line 337:
]
loop thueMorse 6 'bits ->
print bits</langsyntaxhighlight>
 
{{out}}
Line 349:
 
=={{header|AutoHotkey}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">ThueMorse(num, iter){
if !iter
return num
Line 356:
res := ThueMorse(num . opp, --iter)
return res
}</langsyntaxhighlight>
Examples:<langsyntaxhighlight AutoHotkeylang="autohotkey">num := 0
loop 7
output .= A_Index-1 " : " ThueMorse(num, A_Index-1) "`n"
MsgBox % output</langsyntaxhighlight>
{{out}}
<pre>0 : 0
Line 372:
 
=={{header|AWK}}==
<langsyntaxhighlight AWKlang="awk">BEGIN{print x="0"}
{gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</langsyntaxhighlight>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">
<lang BASIC256>
tm = "0"
 
Line 399:
Next j
End
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 406:
 
==={{header|Sinclair ZX81 BASIC}}===
<langsyntaxhighlight lang="basic"> 10 LET T$="0"
20 PRINT "T0=";T$
30 FOR I=1 TO 7
Line 417:
100 NEXT J
110 PRINT T$
120 NEXT I</langsyntaxhighlight>
{{out}}
<pre>T0=0
Line 429:
 
=={{header|BBC BASIC}}==
<langsyntaxhighlight lang="bbcbasic">REM >thuemorse
tm$ = "0"
PRINT tm$
Line 444:
IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"
NEXT
= previous$ + tm$</langsyntaxhighlight>
{{out}}
<pre>0
Line 457:
 
=={{header|BCPL}}==
<langsyntaxhighlight BCPLlang="bcpl">get "libhdr"
 
let parity(x) =
Line 466:
$( for i=0 to 63 do writen(parity(i))
wrch('*N')
$)</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
Line 475:
This implements the algorithm that counts the 1 bits in the binary representation of the sequence number.
 
<langsyntaxhighlight lang="befunge">:0\:!v!:\+g20\<>*:*-!#@_
86%2$_:2%02p2/^^82:+1,+*</langsyntaxhighlight>
 
{{out}}
Line 482:
 
=={{header|BQN}}==
<langsyntaxhighlight lang="bqn">TM ← {𝕩↑(⊢∾¬)⍟(1+⌈2⋆⁼𝕩)⥊0}
 
TM 25 #get first 25 elements</langsyntaxhighlight>
{{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>
Line 491:
===C: Using string operations===
{{trans|Java}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 509:
puts(sequence);
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 517:
 
===C: By counting ones in binary representation of an iterator===
<langsyntaxhighlight Clang="c">#include <stdio.h>
 
/**
Line 541:
 
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 550:
 
===C: By counting ones in binary representation of an iterator (w/User options)===
<langsyntaxhighlight Clang="c"> #include <stdio.h>
 
/**
Line 598:
 
return 0;
} </langsyntaxhighlight>
 
{{out}}
Line 609:
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Text;
 
Line 635:
}
}
}</langsyntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">
#include <iostream>
#include <iterator>
Line 657:
return 0;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 670:
 
=={{header|CLU}}==
<langsyntaxhighlight lang="clu">% Yields an infinite Thue-Morse sequence, digit by digit
tm = iter () yields (char)
n: int := 1
Line 700:
if n = AMOUNT then break end
end
end start_up</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun bit-complement (bit-vector)
(loop with result = (make-array (length bit-vector) :element-type 'bit)
for b across bit-vector
Line 725:
do (print-bit-vector value)))
 
(thue-morse 6)</langsyntaxhighlight>
{{out}}
<pre>
Line 738:
 
=={{header|Cowgol}}==
<langsyntaxhighlight lang="cowgol">include "cowgol.coh";
 
# Find the N'th digit in the Thue-Morse sequence
Line 756:
i := i + 1;
end loop;
print_nl();</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
Line 762:
=={{header|Crystal}}==
{{trans|Javascript}}
<langsyntaxhighlight lang="ruby">steps = 6
 
tmp = ""
Line 774:
}
 
puts s1</langsyntaxhighlight>
 
{{out}}
Line 783:
=={{header|D}}==
{{trans|C}}
<langsyntaxhighlight lang="d">import std.range;
import std.stdio;
 
Line 811:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 827:
 
=={{header|Draco}}==
<langsyntaxhighlight lang="draco">/* Find the N'th digit in the Thue-Morse sequence */
proc nonrec tm(word n) byte:
word n2;
Line 844:
write(tm(i):1)
od
corp</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
Line 851:
{{trans|C#}}
ELENA 4.x :
<langsyntaxhighlight lang="elena">import extensions;
import system'text;
 
Line 870:
{
sequence(6)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 877:
 
=={{header|Elixir}}==
<langsyntaxhighlight lang="elixir">Enum.reduce(0..6, '0', fn _,s ->
IO.puts s
s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end)
Line 885:
Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end)
|> Enum.take(7)
|> Enum.each(&IO.puts/1)</langsyntaxhighlight>
 
{{out}}
Line 906:
 
{{Works with|Office 365 betas 2021}}
<langsyntaxhighlight lang="lisp">thueMorse
=LAMBDA(n,
APPLYN(n)(
Line 917:
)
)(0)
)</langsyntaxhighlight>
 
and also assuming the following generic bindings in the Name Manager for the WorkBook:
 
<langsyntaxhighlight lang="lisp">APPLYN
=LAMBDA(n,
LAMBDA(f,
Line 953:
)
)
)</langsyntaxhighlight>
 
{{Out}}
Line 1,115:
=={{header|Factor}}==
{{works with|Factor|0.98}}
<langsyntaxhighlight lang="factor">USING: io kernel math math.parser sequences ;
 
: thue-morse ( seq n -- seq' )
Line 1,122:
: print-tm ( seq -- ) [ number>string ] map "" join print ;
 
7 <iota> [ { 0 } swap thue-morse print-tm ] each</langsyntaxhighlight>
{{out}}
<pre>
Line 1,136:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<langsyntaxhighlight lang="fortran">program thue_morse
implicit none
logical :: f(32) = .false.
Line 1,148:
end do
end program thue_morse</langsyntaxhighlight>
{{out}}
<pre>
Line 1,160:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
Dim As String tm = "0"
 
Line 1,181:
Next j
End
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,203:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">// prints the first few members of the Thue-Morse sequence
 
package main
Line 1,234:
fmt.Println( tmBuffer.String() )
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,250:
Computing progressively longer prefixes of the sequence:
 
<langsyntaxhighlight lang="haskell">thueMorsePxs :: [[Int]]
thueMorsePxs = iterate ((++) <*> map (1 -)) [0]
 
Line 1,259:
-}
main :: IO ()
main = print $ thueMorsePxs !! 5</langsyntaxhighlight>
{{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>
Line 1,265:
The infinite sequence itself:
 
<langsyntaxhighlight lang="haskell">thueMorse :: [Int]
thueMorse = 0 : g 1
where
Line 1,271:
main :: IO ()
main = print $ take 33 thueMorse</langsyntaxhighlight>
{{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>
Line 1,279:
We only show a prefix of the sequence:
 
<langsyntaxhighlight Jlang="j"> (, -.)@]^:[&0]9
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...</langsyntaxhighlight>
 
Or, more compactly:
 
<langsyntaxhighlight Jlang="j"> ' '-.~":(, -.)@]^:[&0]9
0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110...</langsyntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">public class ThueMorse {
 
public static void main(String[] args) {
Line 1,304:
System.out.println(sb1);
}
}</langsyntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
Line 1,310:
===ES5===
{{trans|Java}}
<langsyntaxhighlight JavaScriptlang="javascript">(function(steps) {
'use strict';
var i, tmp, s1 = '0', s2 = '1';
Line 1,319:
}
console.log(s1);
})(6);</langsyntaxhighlight>
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
 
===ES6===
<langsyntaxhighlight JavaScriptlang="javascript">(() => {
'use strict';
 
Line 1,412:
// MAIN ---
return main();
})();</langsyntaxhighlight>
{{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>
Line 1,421:
 
`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 }
Line 1,430:
| .sb0[.n:]
| explode[]
| . - 48);</langsyntaxhighlight>
'''Example:'''
<syntaxhighlight lang="text">[limit(100;thueMorse)] | join("")</langsyntaxhighlight>
{{out}}
<pre> 0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110
Line 1,440:
{{works with|Julia|0.6}}
 
<langsyntaxhighlight lang="julia">function thuemorse(len::Int)
rst = Vector{Int8}(len)
rst[1] = 0
Line 1,454:
end
 
println(join(thuemorse(100)))</langsyntaxhighlight>
 
{{out}}
Line 1,463:
{{trans|Java}}
The original Java code, as translated to Kotlin, with a few cleanups.
<langsyntaxhighlight lang="kotlin">fun thueMorse(n: Int): String {
val sb0 = StringBuilder("0")
val sb1 = StringBuilder("1")
Line 1,476:
fun main() {
for (i in 0..6) println("$i : ${thueMorse(i)}")
}</langsyntaxhighlight>
 
{{out}}
Line 1,491:
===Kotlin: Alternative===
Same general idea as above, but using a few Kotlin specific code shortcuts.
<langsyntaxhighlight lang="kotlin">fun thueMorse(n: Int): String {
val pair = "0" to "1"
repeat(n) { pair = with(pair) { first + second to second + first } }
Line 1,499:
fun main() {
for (i in 0..6) println("$i : ${thueMorse(i)}")
}</langsyntaxhighlight>
 
{{out}}
Line 1,513:
 
=={{header|Lambdatalk}}==
<langsyntaxhighlight lang="scheme">
 
{def thue_morse
Line 1,528:
-> 0110100110010110100101100110100110010110011010010110100110010110
 
</syntaxhighlight>
</lang>
 
=={{header|Lua}}==
<langsyntaxhighlight Lualang="lua">ThueMorse = {sequence = "0"}
 
function ThueMorse:show ()
Line 1,552:
ThueMorse:show()
ThueMorse:addBlock()
end</langsyntaxhighlight>
{{out}}
<pre>0
Line 1,561:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang Mathematica="mathematica">ThueMorse[Range[20]]</langsyntaxhighlight>
{{out}}
<pre>{1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0}</pre>
 
=={{header|Modula-2}}==
<langsyntaxhighlight lang="modula2">MODULE ThueMorse;
FROM Strings IMPORT Concat;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,591:
Sequence(6);
ReadChar;
END ThueMorse.</langsyntaxhighlight>
 
=={{header|NewLISP}}==
 
<langsyntaxhighlight lang="newlisp">(define (Thue-Morse loops)
(setf TM '(0))
(println TM)
Line 1,610:
(Thue-Morse 5)
(exit)
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,625:
 
===Using an iterator and sequences concatenations===
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils
 
iterator thueMorse(maxSteps = int.high): string =
Line 1,637:
 
for bits in thueMorse(6):
echo bits</langsyntaxhighlight>
 
{{out}}
Line 1,648:
 
===Using fast sequence generation algorithm from Wikipedia===
<langsyntaxhighlight Nimlang="nim">type Bit = 0..1
 
proc thueMorse(seqLength: Positive): string =
Line 1,658:
result.add chr(val + ord('0'))
 
echo thueMorse(64)</langsyntaxhighlight>
 
{{out}}
Line 1,664:
 
=={{header|OASYS Assembler}}==
<langsyntaxhighlight lang="oasys_oaa">; Thue-Morse sequence
 
[*'A] ; Ensure the vocabulary is not empty
Line 1,681:
%@FO> ; Reset object pointer
CR ; Line break
| ; Repeat loop</langsyntaxhighlight>
The standard DOS-based interpreter will display an error message about word too long after 7 lines are output; this is because the 8th line does not fit in 80 columns.
 
=={{header|Objeck}}==
{{trans|Java}}
<langsyntaxhighlight lang="objeck">class ThueMorse {
function : Main(args : String[]) ~ Nil {
Sequence(6);
Line 1,702:
}
}
</syntaxhighlight>
</lang>
 
Output:
Line 1,712:
===By counting ones in binary representation of an iterator===
{{trans|C}}
<langsyntaxhighlight lang="ocaml">(* description: Counts the number of bits set to 1
input: the number to have its bit counted
output: the number of bits set to 1 *)
Line 1,730:
| _ -> assert false)
done;
print_newline ()</langsyntaxhighlight>
 
 
===Using string operations===
{{trans|Objeck}}
<langsyntaxhighlight lang="ocaml">let sequence steps =
let sb1 = Buffer.create 100 in
let sb2 = Buffer.create 100 in
Line 1,748:
 
let () =
print_endline (sequence 6);</langsyntaxhighlight>
 
=={{header|Pascal}}==
Line 1,754:
{{works with|Delphi}}
Like the C++ Version [[http://rosettacode.org/wiki/Thue-Morse#C.2B.2B]] the lenght of the sequence is given in advance.
<langsyntaxhighlight lang="pascal">Program ThueMorse;
function fThueMorse(maxLen: NativeInt):AnsiString;
Line 1,812:
fThueMorse(1 shl 30);
{$IFNDEF LINUX}readln;{$ENDIF}
end.</langsyntaxhighlight>
{{Output}}<pre>Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi
without -O4 -> 2 secs
Line 1,829:
=={{header|Perl}}==
{{works with|Perl|5.x}}
<langsyntaxhighlight lang="perl">sub complement
{
my $s = shift;
Line 1,844:
$str .= complement($str);
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,857:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #004080;">string</span> <span style="color: #000000;">tm</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0"</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
Line 1,863:
<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>
<!--</langsyntaxhighlight>-->
{{Out}}
<pre>
Line 1,877:
 
=={{header|Phixmonti}}==
<langsyntaxhighlight Phixmontilang="phixmonti">def inverte
dup len
for
Line 1,890:
dup print nl nl
inverte chain
endfor</langsyntaxhighlight>
 
=={{header|PHP}}==
Line 1,898:
(see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence)
 
<langsyntaxhighlight PHPlang="php"><?php
 
function thueMorseSequence($length) {
Line 1,914:
for ($n = 10 ; $n <= 100 ; $n += 10) {
echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL;
}</langsyntaxhighlight>
 
{{out}}
Line 1,929:
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(let R 0
(prinl R)
(for (X 1 (>= 32 X))
Line 1,938:
(bin (x| (dec (** 2 X)) R)) ) ) )
(prinl (pack 0 (bin R)))
(inc 'X X) ) )</langsyntaxhighlight>
 
=={{header|PowerShell}}==
<langsyntaxhighlight lang="powershell">function New-ThueMorse ( $Digits )
{
# Start with seed 0
Line 1,971:
New-ThueMorse 5
New-ThueMorse 16
New-ThueMorse 73</langsyntaxhighlight>
{{out}}
<pre>01101
Line 1,979:
=={{header|PureBasic}}==
{{trans|C}}
<langsyntaxhighlight PureBasiclang="purebasic">EnableExplicit
 
Procedure.i count_bits(v.i)
Line 1,996:
Next
PrintN(~"\n...fin") : Input()
EndIf</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110
Line 2,003:
=={{header|Python}}==
===Python: By substitution===
<syntaxhighlight lang="python">
<lang Python>
m='0'
print(m)
Line 2,013:
m=m0+m
print(m)
</syntaxhighlight>
</lang>
{{out}}
<pre>0
Line 2,024:
 
===Python: By counting set ones in binary representation===
<syntaxhighlight lang="python">
<lang Python>
>>> def thue_morse_digits(digits):
... return [bin(n).count('1') % 2 for n in range(digits)]
Line 2,032:
 
>>>
</syntaxhighlight>
</lang>
 
===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]===
<syntaxhighlight lang="python">
<lang Python>
>>> def thue_morse_subs(chars):
... ans = '0'
Line 2,045:
'01101001100101101001'
>>>
</syntaxhighlight>
</lang>
 
===Python: By pair-wise concatenation===
<syntaxhighlight lang="python">
<lang Python>
>>> def thue_morse(n):
... (v, i) = ('0', '1')
Line 2,058:
'0110100110010110100101100110100110010110011010010110100110010110'
>>>
</syntaxhighlight>
</lang>
 
=={{header|Quackery}}==
This uses the [https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Fast_sequence_generation fast sequence generation algorithm] from the wiki article.
<langsyntaxhighlight lang="quackery">[ [] 0 rot times
[ i^ dup 1 - ^
dup 1 >> ^ hex 55555555 & if
Line 2,069:
[ digit join ] ] drop ] is thue-morse ( n --> $ )
 
20 thue-morse echo$ cr</langsyntaxhighlight>
{{out}}
<pre>
Line 2,076:
 
=={{header|R}}==
<langsyntaxhighlight lang="rsplus">
thue_morse <- function(steps) {
sb1 <- "0"
Line 2,088:
}
cat(thue_morse(6), "\n")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,095:
 
=={{header|Racket}}==
<langsyntaxhighlight lang="racket">#lang racket
(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))
(define (thue-morse-step (s "0"))
Line 2,104:
(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))
 
(for-each displayln (thue-morse 7))</langsyntaxhighlight>
{{out}}
<pre>0
Line 2,118:
{{Works with|rakudo|2018.03}}
First 8 of an infinite sequence
<syntaxhighlight lang="raku" perl6line>.say for (0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *)[^8];</langsyntaxhighlight>
 
{{out}}
Line 2,134:
===using functions===
Programming note: &nbsp; ''pop count'' &nbsp; (or &nbsp; ''weight'') &nbsp; is the number of &nbsp; <b>1</b>'s &nbsp; bits in the binary representation of a number.
<langsyntaxhighlight lang="rexx">/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/
Line 2,145:
/*──────────────────────────────────────────────────────────────────────────────────────*/
$pop: return length( space( translate( arg(1), , 0), 0) ) /*count 1's in number.*/
$weight: return $pop( x2b( d2x( arg(1) ) ) ) /*dec──►bin, pop count*/</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,152:
 
===using in-line code===
<langsyntaxhighlight lang="rexx">/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/
Line 2,159:
$= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2 /*append to $.*/
end /*j*/
say $ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}} <br>
 
Line 2,166:
 
Because of this, the displaying of the output lacks the granularity of the first two REXX versions.
<langsyntaxhighlight lang="rexx">/*REXX pgm generates & displays the Thue─Morse sequence up to the Nth term (inclusive). */
parse arg N . /*obtain the optional argument from CL.*/
if N=='' | N=="," then N= 6 /*Not specified? Then use the default.*/
Line 2,173:
$= $ || translate($, 10, 01) /*append $'s complement to $ string.*/
end /*j*/
say $ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 2,180:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
tm = "0"
see tm
Line 2,195:
see nl
return (previous + tm)
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,208:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">puts s = "0"
6.times{puts s << s.tr("01","10")}</langsyntaxhighlight>
 
{{out}}
Line 2,223:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">const ITERATIONS: usize = 8;
 
fn neg(sequence: &String) -> String {
Line 2,239:
sequence = format!("{}{}", sequence, neg(&sequence));
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,254:
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">def thueMorse(n: Int): String = {
val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1"))
(0 until n).foreach { _ =>
Line 2,264:
}
 
(0 to 6).foreach(i => println(s"$i : ${thueMorse(i)}"))</langsyntaxhighlight>
{{Out}} See it running in your browser by [https://scastie.scala-lang.org/rsF3Y5ABQoK0zZMMA3m6Ow Scastie (JVM)].
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func recmap(repeat, seed, transform, callback) {
func (repeat, seed) {
callback(seed)
Line 2,275:
}
 
recmap(6, "0", {|s| s + s.tr('01', '10') }, { .say })</langsyntaxhighlight>
{{out}}
<pre>
Line 2,289:
=={{header|SQL}}==
This example is using SQLite.
<langsyntaxhighlight SQLlang="sql">with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select * from a;</langsyntaxhighlight>
You can add a LIMIT clause to the end to limit how many lines of output you want.
 
Line 2,296:
Since <tt>string map</tt> correctly handles overlapping replacements, the simple map <tt>0 -> 01; 1 -> 10</tt> can be applied with no special handling:
 
<langsyntaxhighlight Tcllang="tcl">proc tm_expand {s} {string map {0 01 1 10} $s}
# this could also be written as:
# interp alias {} tm_expand {} string map {0 01 1 10}
Line 2,306:
}
return $s
}</langsyntaxhighlight>
 
Testing:
 
<langsyntaxhighlight Tcllang="tcl">for {set i 0} {$i <= 6} {incr i} {
puts [tm $i]
}</langsyntaxhighlight>
 
{{out}}
Line 2,325:
For giggles, also note that the above SQL solution can be "natively" applied in Tcl8.5+, which bundles Sqlite as a core extension:
 
<syntaxhighlight lang="tcl">
<lang Tcl>
package require sqlite3 ;# available with Tcl8.5+ core
sqlite3 db "" ;# create in-memory database
Line 2,331:
db eval {with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select a from a limit $LIMIT} {
puts $a
}</langsyntaxhighlight>
 
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">For x = 0 to 6 ' sequence loop
Print Using "_#";x;": "; ' print sequence
For y = 0 To (2^x)-1 ' element loop
Line 2,351:
a@ = SHL(a@, -1) ' shift the number
Loop
Return (b@) ' return number of bits set</langsyntaxhighlight>
{{Out}}
<pre> 0: 0
Line 2,364:
 
=={{header|VBA}}==
<langsyntaxhighlight lang="vb">Option Explicit
 
Sub Main()
Line 2,385:
End If
Thue_Morse = s & k
End Function</langsyntaxhighlight>
{{Out}}
<pre>1:=> 0
Line 2,398:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Text
 
Module Module1
Line 2,417:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>
Line 2,423:
=={{header|Wren}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="ecmascript">var thueMorse = Fn.new { |n|
var sb0 = "0"
var sb1 = "1"
Line 2,434:
}
 
for (i in 0..6) System.print("%(i) : %(thueMorse.call(i))")</langsyntaxhighlight>
 
{{out}}
Line 2,448:
 
=={{header|XLISP}}==
<langsyntaxhighlight lang="lisp">(defun thue-morse (n)
(defun flip-bits (s)
(defun flip (l)
Line 2,470:
; test THUE-MORSE by printing the strings it returns for n = 0 to n = 6
 
(mapcar (lambda (n) (print (thue-morse n))) (range 0 7))</langsyntaxhighlight>
{{out}}
<pre>"0"
Line 2,481:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">string 0; \use zero-terminated strings
char Thue;
int N, I, J;
Line 2,497:
J:= J+I; \set index to terminator
];
]</langsyntaxhighlight>
 
{{out}}
Line 2,512:
=={{header|Yabasic}}==
{{trans|Phix}}
<langsyntaxhighlight Yabasiclang="yabasic">tm$ = "0"
for i=1 to 8
? tm$
Line 2,525:
next
return tm$
end sub</langsyntaxhighlight>
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }</langsyntaxhighlight>
"12233334444" - "23"-->"14444"
<langsyntaxhighlight lang="zkl">str:="0"; do(7){ str=nextTM(str.println()) }</langsyntaxhighlight>
println() returns the result it prints (as a string).
{{trans|Java}}
<langsyntaxhighlight lang="zkl">fcn nextTM2{
var sb1=Data(Void,"0"), sb2=Data(Void,"1");
r:=sb1.text; sb1.append(sb2); sb2.append(r);
r
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">do(7){ nextTM2().println() }</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328605"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information