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

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

Perl 6

<lang perl6>my @tm := 0, -> *@s { @s.map({ + not $_ }) } ... *;

say @tm[^64].join;</lang>

Output:

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>

zkl

<lang zkl>fcn next(str){ str.pump(str,fcn(c){ (0x61 - c.toAsc()).toChar() }) }</lang> <lang zkl>str:="0"; do(7){ str.println(); str=next(str) }</lang>

Output:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110