Thue-Morse 序列的一种构造方法

1、把一个整数转化为二进制数。比如，9999的二进制形式是10011100001111。

2、数一下这个二进制数里面的1出现的次数。

3、定义一个函数f(n)：自变量n是十进制的非负整数；如果艘绒庳焰n的二进制形式里面的1出现的次数是偶数，就返回0；否则返回1。

4、这样，就可以构造Thue-Morse 序列。下图给出了Thue-Morse 序列的前11个数字。

5、下面是前100个数字。

6、观察序列的前4*n个数字（n是正整数），可以发现某种对称关系。从中间截断，两边相加，全部是1。

7、于是，下面给出另一种构造方法。先给出序列的前两个数字01；然后用01替换0，用10替换1。

8、用第二个方法构造的序列长度的增长速度很快。