这些序列都是自相似序列……

如果说数学家是魔术师的话，无穷就是一根最强大的魔杖。在Manfred Schröder的一篇题为Fractals in Music的论文里，作者提到，把每个正整数对应的二进制数中“1”的个数依次写下来，得到的数列有一个很神奇的性质：划掉所有的奇数项，得到的序列仍然是整个序列本身。

十进制数  1   2   3    4    5    6    7     8     9    10    11    12    13    14
二进制数  1  10  11   100  101  110  111  1000  1001  1010  1011  1100  1101  1110
1的个数   1   1   2    1    2    2    3     1     2     2     3     2     3     3
取偶数项      1        1         2          1           2           2           3

最初我是在《算法艺术与信息学竞赛》里见到这个东西的，当时硬是被震撼住了。这样的序列叫做“自相似序列”，意思是说自己的一部分等于本身。注意到，这个“自相似”可以无限制地进行下去。再次取出所得的序列中的偶数项，结果还是与最初的序列一样；再这样做下去做无数次，每一次的结果都会与原始序列相同。也就是说，无穷里面包含了无穷多个规模不同的无穷，并且所有这些无穷都和原来完全相同。不过呢，仔细一想你会发现这个一点也不奇怪，奥妙就在于，n和2n的二进制表达中唯一的差别就是末尾的那个“0”。

类似的序列还有很多。今天偶然踩进了这个网页(http://www.research.att.com/~njas/sequences/selfsimilar.html)，发现能叫出名字的自相似序列起码还有几十个。仅在二进制上面做文章的就有好几个，有趣的如：

A030101(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A030101) 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 13, 3, 11, 7, 15, 1, 17, 9, 25 … n的二进制表达逆序之后的值

A038189(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A038189) 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0 … n的二进制表达中，最右边的数字“1”左边的数字

A020987(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A020987) 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0 … Golay-Rudin-Shapiro序列，n的二进制中“11”出现次数的奇偶性

另一些比较神奇的还有：

A000161(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000161) 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1 … 将n表示为两个数的平方和的方案数

A001316(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001316) 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4 … Gould序列，杨辉三角第n行的奇数项个数

A016725(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A016725) 6, 6, 30, 6, 30, 30, 54, 6, 102, 30, 78, 30, 78, 54, 150 … x^2+y^2+z^2 = n^2的非负整数解的个数

A046109(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A046109) 4, 4, 4, 4, 12, 4, 4, 4, 4, 12, 4, 4, 12, 4, 12, 4, 12, 4 … 以原点为圆心半径为n的圆所经过的整数格点的个数

A053866(http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A053866) 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0 … n的约数和的奇偶性