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.
Programming Praxis 
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; }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.
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)))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:
def nth_tm(n): s = '0' for _ in range(n): s += ''.join(str('10'.index(c)) for c in s) return sHere’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]:
#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"; }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); } }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 6996966996696996966969966996966996696996699696696996966996696996OK, 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)))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:>
*/
/* 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:> */@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:
#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.
@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;
}
}