Thue-Morse Sequence

September 30, 2014

Mathematicians are strange people. As an example, I offer the Thue-Morse sequence, which is a binary sequence of 0’s and 1’s that never repeats, obtained by starting with a single 0 and successively appending the binary complement of the sequence. Thus, term 0 of the sequence is (0), term 1 of the sequence is (0 1), term 2 of the sequence is (0 1 1 0), term 3 of the sequence is (0 1 1 0 1 0 0 1), term 4 of the sequence is (0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0), and so on; to calculate term 3 from term 2, we started with term 2 (0 1 1 0), complemented each element of the term (1 0 0 1), then appended the two (0 1 1 0 1 0 0 1). That looks useless to me, but mathematicians have been excited by it since 1851, hence my conclusion that mathematicians are strange people.

Your task is to write a program that generates the nterm of the Thue-Morse sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

20 Responses to “Thue-Morse Sequence”

  1. Binary complement of a ascii string representing a binary number is achieved by “xor”ing with (chr 1) basically flips the last bit!

    use strict;
    use feature 'say';
    
    say thue_morse(6);
    
    sub thue_morse {
      my ($n,$t,$x) = (shift,'0',chr 1); 
      ($t,$x) = ($t.$t^$x,$x.$x) foreach 1 .. $n;
      return $t;
    }
    
  2. Andras said

    Please give me shorter Java solution :)

    private static String thueMorse(int term) {
    return term == 0 ? “0” : thueMorse(term – 1)
    + thueMorse(term – 1).replaceAll(“0”, “x”).replaceAll(“1”, “0”).replaceAll(“x”, “1”);
    }

    @Test
    public void testThueMorse() throws Exception {
    assertThat(thueMorse(0)).isEqualTo(“0”);
    assertThat(thueMorse(1)).isEqualTo(“01”);
    assertThat(thueMorse(2)).isEqualTo(“0110”);
    assertThat(thueMorse(3)).isEqualTo(“01101001”);
    assertThat(thueMorse(4)).isEqualTo(“0110100110010110”);
    }

  3. Jussi Piitulainen said

    Python 3, translating 0 to 01, 1 to 10, n-fold.

    from functools import reduce
    tt = str.maketrans({'0':'01','1':'10'})
    nth = lambda n : reduce(lambda s, t : s.translate(tt), range(n), '0')
    print(*map(nth, range(6)))
    
  4. Jussi Piitulainen said

    And here’s a shorter Java solution :)

    private static String thueMorse(int term) {
    return term == 0 ? "0" :
    thueMorse(term - 1).replaceAll("0", "x").replaceAll("1", "10").replaceAll("x", "01");
    }

  5. Francesco said

    Haskell:

    tms p = iterate (\as -> as ++ map (\i -> mod (i+1) 2) as) [0] !! p
  6. Mark said
    def nth_tm(n):
        s = '0'
        for _ in range(n):
            s += ''.join(str('10'.index(c)) for c in s)
        return s
    
  7. matthew said

    Here’s a slightly silly Haskell solution:

    -- Binary tree
    data Tree a = Empty | Node a (Tree a) (Tree a)
    
    -- Print nodes at level n
    scan _ Empty = []
    scan 0 (Node a _ _) = [a]
    scan n (Node _ t1 t2) = scan (n-1) t1 ++ scan (n-1) t2
    
    -- A couple of infinite trees
    one = Node 1 one zero
    zero = Node 0 zero one
    
    main = print (scan 4 zero)
    
  8. matthew said

    A slightly sillier C++ solution. Keep a mask of all but the top bit of the current index, use this to set s[2^n+k] to !s[k]:

    #include <string>
    #include <iostream>
    #include <stdlib.h>
    #include <stdint.h>
    
    typedef uint32_t T;
    int main(int argc, char *argv[])
    {
       T n = strtoul(argv[1],NULL,0);
       T m = 0; // Bitmask for lower bits
       std::string s = "0";
       for (T i = 1; i < n; i++) {
         m |= i>>1;
         s.push_back(('0'+'1')-s[i&m]);
       }
       std::cout << s << "\n";
    }
    
  9. matthew said

    Or, for another solution, directly compute each value from the parity of the count of set bits – we can use the gcc popcount intrinsic for this:

    #include <stdio.h>
    int main()
    {
      for (unsigned long i = 0; ; i++) {
        putchar('0' + __builtin_popcountl(i)%2);
      }
    }
    
  10. matthew said

    And finally, a simpler recurrence (and we can do 32 bits at a time, though the result is not much different):

    #include <vector>
    #include <iostream>
    #include <stdlib.h>
    #include <stdint.h>
    typedef uint32_t T;
    int main(int argc, char *argv[])
    {
      int n = strtol(argv[1],NULL,0);
      std::vector<T> s(2*n);
      s[0] = 0x69969669U;
      for (int i = 0; i < n; i++) {
        s[2*i] = s[i];
        s[2*i+1] = ~s[i];
       }
      for (T i: s) std::cout << std::hex << i;
      std::cout << "\n";
    }
    
    $ g++ -std=c++11 -Wall mt.cpp -o mt
    $ ./mt 4
    6996966996696996966969966996966996696996699696696996966996696996
    
  11. matthew said

    OK, here’s just one more: a purely numeric solution, Python for bignums and binary output (it’s just the “append the complement” method really):

    def mt(n):
        m,p = 0,2
        while n > 0: m,p,n = (p-1)*(m+1),p*p,n-1
        return m
    
    for n in range(10): print("0{0:b}".format(mt(n)))
    
  12. matthew said

    Definitely the last one for now:

    #!/usr/bin/runghc
    interleave (a:s) t = a:interleave t s
    s = 0:interleave (map (1-) s) (tail s)
    main = print (take 32 s)
    
  13. Andras said

    @Jussi Piitulainen: Great thanks :)

  14. Claire said

    C++ Version:
    This seems a little stupid, but it does work well.

    string ThueMorse::GenerateThueMorse(int n)
    {
    long bit = 0;
    string sequence = “”;
    char a[10];
    itoa(bit,a,10);
    sequence.append(a);
    string result=””;
    result += sequence;
    for( int i =1; i <=n ;i++)
    {
    for (int i=0; i<sequence.length();i++)
    {
    if(sequence.at(i)=='0')
    sequence[i] = '1';
    else
    sequence[i] = '0';
    }

    result.append(sequence);
    sequence = result;
    cout<<"result is "<<result<<endl;
    }

    return result;
    }

  15. Robert said

    /* https://programmingpraxis.com/2014/09/30/thue-morse-sequence/, R Bassett, Oct 2014 */

    #include
    #include

    void thuemorse (int d, int depth)
    {
    if (depth 1)
    depth = atoi (argv[1]);
    if (depth 2)
    t0 = atoi (argv[2]) ? 1 : 0;

    thuemorse (t0, depth);
    putchar (‘\n’);
    return 0;
    }

    /*
    C:> thue-morse 0
    0

    C:> thue-morse 0 1
    1

    C:> thue-morse 1
    01

    C:> thue-morse 2
    0110

    C:> thue-morse 3
    01101001

    C:> thue-morse 4
    0110100110010110

    C:> thue-morse 4 1
    1001011001101001

    C:>
    */

  16. rbassett99 said
    /* https://programmingpraxis.com/2014/09/30/thue-morse-sequence/, R Bassett, Oct 2014 */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void thuemorse (int d, int depth)
    {
    	if (depth <= 0) 
    		putchar (d ? '1' : '0'); 
    	else if (d) {
    		thuemorse (1, depth - 1);
    		thuemorse (0, depth - 1);
    	} else {
    		thuemorse (0, depth - 1);
    		thuemorse (1, depth - 1);
    	}
    }
    
    int main (int argc, char **argv)
    {
    	int t0 = 0;     /* term 0 is {0} */
    	int depth = 0;  /* 0 means stop at term 0; 1 means stop at term 1; ... */
    
    	if (argc > 1) 
    		depth = atoi (argv[1]);
    	if (depth < 0) 
    		depth = 0;
    	if (argc > 2) 
    		t0 = atoi (argv[2]) ? 1 : 0;
    
    	thuemorse (t0, depth);
    	putchar ('\n');
    	return 0;
    }
    
    /*
    C:> thue-morse 0
    0
    
    C:> thue-morse 0 1
    1
    
    C:> thue-morse 1
    01
    
    C:> thue-morse 2
    0110
    
    C:> thue-morse 3
    01101001
    
    C:> thue-morse 4
    0110100110010110
    
    C:> thue-morse 4 1
    1001011001101001
    
    C:>
    */
    
  17. Claire said

    @rbassett99 : Wow, yours is much better. Learn a lot from yours. Thanks a lot:)

  18. matthew said

    @Claire: here’s another version of your solution with the initialization of the result tidied up a bit; also, we can get rid of the extra ‘sequence’ string and build up the result directly in the result:

    #include <iostream>
    #include <string>
    std::string thuemorse(int n)
    {
      std::string result = "0";
      for (int i=0; i<n; i++) {
        int slen = result.length();
        result.resize(2*slen);
        for (int i=0; i<slen; i++) {
          if (result[i]=='0')
            result[i+slen] = '1';
          else
            result[i+slen] = '0';
        }
      }
      return result;
    }
    
    int main()
    {
      std::cout << thuemorse(6) << "\n";
    }
    

    Robert’s recursive solution is nice too of course.

  19. Claire said

    @matthew: Thank your for your improvement. It seems great!:)

  20. Lighttheworld said

    public String seq(int n){
    if(n==0){
    return “0”;
    }else{
    String s = seq(n-1);
    String ss = “”;
    for(int i=0;i<s.length();i++){
    if(s.charAt(i)== '0'){
    ss+="1";
    }else {
    ss+="0";
    }
    }
    return s+ss;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: