Thue-Morse

Thue-Morse is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

1. include <iostream>
2. include <iterator>
3. 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)

1. 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

Works with: rakudo version 2015-12-22

<lang perl6>my @tm = 0, { '0' ~ @_.join.trans( "01" => "10", :g) } ... *;

.say for @tm[^8];</lang>

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

PicoLisp

<lang 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) ) )</lang>

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 1^st 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. <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=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  $.    */
      end   /*j*/

say $ /*stick a fork in it, we're all done. */</lang> output   when using the default input:

0110100110010110100101100110100110010110011010010110100110010110

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}

1. this could also be written as:
2. 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).

Translation of: Java

<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