## Thue-Morse Sequence

### September 30, 2014

This is about as easy as it looks:

```(define (complement digits)   (map (lambda (d) (if (zero? d) 1 0)) digits))```

```(define (thue-morse n)   (let loop ((tms '(0)) (n n))     (if (zero? n) tms       (loop (append tms (complement tms)) (- n 1)))))```

And here we calculate the 6th term of the Thue-Morse sequence:

```> (thue-morse 6) (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)```

Beware that the sequence grows exponentially, as does the time it takes to calculate it. You can run the program at http://programmingpraxis.codepad.org/5mdIPU3e.

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

`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

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;
}
}