Thue-Morse
Make Thue-Morse sequence.
AWK
<lang AWK>BEGIN{print x="0"} {gsub(/./," &",x);gsub(/ 0/,"01",x);gsub(/ 1/,"10",x);print x}</lang>
C++
<lang cpp>
- 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;
} </lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Elixir
<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)
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)</lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
Haskell
<lang haskell>import Control.Monad
thueMorse = ap (++) (map (1-)) `iterate` [0]</lang>
Output: <lang haskell>~> thueMorse !! 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]</lang>
J
We only show a prefix of the sequence:
<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 ...</lang>
Java
<lang 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); }
}</lang>
0110100110010110100101100110100110010110011010010110100110010110
OASYS Assembler
<lang oasys_oaa>; 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</lang> 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.
Perl 6
<lang perl6>my @tm = 0, { @_.map: + ! * } ... *;
say @tm[^64].join;</lang>
- Output:
0110100110010110100101100110100110010110011010010110100110010110
Racket
<lang 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))</lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110
REXX
using functions
Programming note: pop count (or weight) is the number of 1's bits in the binary representation of a number. <lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ 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*/</lang> output when using the default input:
01101001100101101001011001101001100101100110100101101001100101101001011001101001
using in-line code
<lang rexx>/*REXX program generates & displays the Thue─Morse sequence up to the Nth item*/ 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 it to $.*/ end /*j*/
say $ /*stick a fork in it, we're all done. */</lang>
output is identical to the 1st REXX version.
SQL
This example is using SQLite. <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;</lang> 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:
<lang 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}
proc tm {k} {
set s 0 while {[incr k -1] >= 0} { set s [tm_expand $s] } return $s
}</lang>
Testing:
<lang Tcl>for {set i 0} {$i <= 6} {incr i} {
puts [tm $i]
}</lang>
- 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:
<lang Tcl> 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
}</lang>
zkl
<lang zkl>fcn nextTM(str){ str.pump(str,'-.fp("10")) } // == fcn(c){ "10" - c }) }</lang> "12233334444" - "23"-->"14444" <lang zkl>str:="0"; do(7){ str=nextTM(str.println()) }</lang> println() returns the result it prints (as a string).
<lang zkl>fcn nextTM2{
var sb1=Data(Void,"0"), sb2=Data(Void,"1"); r:=sb1.text; sb1.append(sb2); sb2.append(r); r
}</lang> <lang zkl>do(7){ nextTM2().println() }</lang>
- Output:
0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 0110100110010110100101100110100110010110011010010110100110010110