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

电脑

python3+

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

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

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

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

下面是前100个数字。

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

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

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