## 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 *n*term 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.

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

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”);

}

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

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");

}

Haskell:

Here’s a slightly silly Haskell solution:

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]:

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:

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

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):

Definitely the last one for now:

@Jussi Piitulainen: Great thanks :)

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;

}

/* 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:>

*/

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

@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:

Robert’s recursive solution is nice too of course.

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

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;

}

}