主题
Search

Thue-Morse 序列

下载 Mathematica 笔记本下载 Wolfram 笔记本

Thue-Morse 序列，也称为 Morse-Thue 序列或 Prouhet-Thue-Morse 序列 (Allouche and Cosnard 2000)，是由非负整数的二进制表示中 1 的计数奇偶性获得的一系列相关数字序列之一。

直接取奇偶性得到的版本是

t_n=s_2(n) (mod 2),
(1)

其中 s_2(n) 是二进制数字和。对于 n=0, 1, 2, ...，前几个项由 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, ... 给出 (OEIS A010060; Allouche and Shallit 2003, pp. 15 和 153)。通过取二进制补码获得的序列的另一种形式由 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, ... 给出 (OEIS A010059; Wolfram 2002, p. 890)。

将 Thue-Morse 序列解释为串联的二进制数字，得到Thue-Morse 常数。

Thue-Morse sequence recurrence plot

上面说明了 Thue-Morse 序列的递归图。

存在一组惊人的涉及 Thue-Morse 序列 {t_n} 的乘积，由下式给出

product_(n=0)^(infty)((2n+1)/(2n+2))^((-1)^(t_n))=(sqrt(2))/2
(2)
product_(n=0)^(infty)((2n+1)/(2n+2))^(2t_n)((2n+3)/(2n+2))=(2sqrt(2))/pi
(3)
product_(n=0)^(infty)((2n+1)/(2n+2))^(2(1-t_n))((2n+3)/(2n+2))=(sqrt(2))/pi
(4)

(Allouche and Shallit 2003, pp. 153 和 204，更正了两个排印错误)，其中第一个归因于 Woods (1978) 和 Robbins (1979)，是 Sondow (2006) 的数字和恒等式的特殊情况 b=2。

令人惊奇的是，Thue-Morse 序列可以从替换系统生成

0->01
(5)
1->10
(6)

得到

0->01->0110->01101001->...
(7)

当从 0 开始时，以及

1->10->1001->10010110->...
(8)

从 1 开始时。将这些序列解释为十进制数，得到序列 0, 1, 6, 105, 27030, 1771476585, ... (OEIS A048707) 和 1, 2, 9,1 50, 38505, 2523490710, ...，分别地。在初始生成之后，每个子序列生成都有 2^n 个 0 和 2^n 个 1。

Wolfram (2002) 提供了各种Wolfram 语言代码，这些代码生成了补码 Thue-Morse 序列 1, 0, 0, 1, 0, 0, 1, ... 的前 2^k 项，计算如下

1. 替换系统，

2. 邪恶数的位置，这些数在其二进制展开式中具有偶数个 1 (OEIS A001969)，

3. 生成函数，遵循 0->1, 1->-1,

4. 元胞自动机 (Wolfram 2002, p. 1186),

5. 代数生成函数,

6. 以超几何函数表示的闭式表达式。

  (* 1 *)
  Nest[Join[#, 1 - #]&, {1}, k]
  (* 2 *)
  Table[1 - Mod[DigitCount[n - 1, 2, 1], 2],
    {n, 2^k}]
  (* 3 *)
  (CoefficientList[Product[1 - z^(2^s),
    {s, 0, k - 1}], z] + 1)/2
  (* 4 *)
  Flatten[CellularAutomaton[{69540422, 2, 2},
    {{1}, 0}, 2^k - 1, {All, 0}]]
  (* 5 *)
  Mod[CoefficientList[Series[(1 + Sqrt[(1 - 3 x)/
    (1 + x)])/(2 (1 + x)), {x, 0, 2^k - 1}], x], 2]
  (* 6 *)
  Mod[Table[(-1)^n/2 + (-3)^n Sqrt[Pi] *
    Hypergeometric2F1Regularized[3/2, - n, 3/2 - n, - 1/3]/
      (4 n!), {n, 0, 2^k - 1}], 2]

将序列写成 有限域 GF(2) 上的幂级数，

F(x)=0+1x+1x^2+0x^3+1x^4+...,
(9)

那么 F 满足二次方程

(1+x)F^2+F=x/(1+x^2) (mod 2).
(10)

这个方程有两个解，F 和 F^'，其中 F^' 是 F 的补码，即，

F+F^'=1+x+x^2+x^3+...=1/(1+x),
(11)

这与二次方程的根之和的公式一致。等式 (10) 可以如下证明。令 (abcdef...) 是 幂级数 的简写

a+bx+cx^2+dx^3+...,
(12)

所以 F(x) 是 (0110100110010110...)。要得到 F^2，只需使用在 GF(2) 上平方幂级数的规则

(A+B)^2=A^2+B^2 (mod 2),
(13)

这扩展到平方幂级数的简单规则

(a_0+a_1x+a_2x^2+...)^2=a_0+a_1x^2+a_2x^4+... (mod 2),
(14)

即，将序列按因子 2 展开，(0 1 1 0 1 0 0 1 ...)，并在奇数位置插入零以得到

F^2=(0010100010000010...).
(15)

然后乘以 x (这只是在前面添加一个零) 得到

xF^2=(00010100010000010...).
(16)

加到 F^2 得到

(1+x)F^2=(0011110011000011...).
(17)

这是二次方程的第一项，它是 Thue-Morse 序列，每一项都加倍了。下一项是 F，所以我们有

(1+x)F^2=(0011110011000011...)
(18)
F=(0110100110010110...).
(19)

总和是上面两个序列 异或 在一起 (没有进位，因为我们在 GF(2) 上工作)，得到

(1+x)F^2+F=(0101010101010101...).
(20)

因此我们有

(1+x)F^2+F=x/(1+x^2)=x+x^3+x^5+x^7+x^9+x^(11)+... (mod 2).
(21)

Thue-Morse 词是无重叠的 (Allouche and Shallit 2003, p. 15)，因此也是在两个符号上无立方的 (Morse and Hedlund 1944)。因此，该序列不包含形式为 WWW 的子串，其中 W 是任何词。例如，它不包含词 000、010101 或 010010010。事实上，以下更强的陈述是正确的：Thue-Morse 序列不包含任何形式为 WWa 的子串，其中 a 是 W 的第一个符号。我们可以通过执行以下操作在三个符号上获得无平方序列：取 Thue-Morse 序列 0110100110010110... 并查看出现的长度为 2 的词序列：10 01 10 00 01 11 10 .... 将 01 替换为 0，10 替换为 1，00 替换为 2，11 替换为 2，得到以下序列：1012021.... 那么这个序列是无平方的 (Morse and Hedlund 1944)。

Thue-Morse 序列与格雷码有着重要的联系。Kindermann 使用 Thue-Morse 序列的自相似性生成分形音乐。

参见

邪恶数, 数字计数, 格雷码, 梅菲斯特圆舞曲序列, 奇偶性, 兔子序列, Thue-Morse 常数, Thue 序列

在 Wolfram|Alpha 中探索

参考文献

Allouche, J.-P. 和 Cosnard, M. "Komornik-Loreti 常数是超越数。" Amer. Math. Monthly 107, 448-449, 2000.Allouche, J.-P. 和 Shallit, J. "无处不在的 Prouhet-Thue-Morse 序列。" 在 序列及其应用，SETA'98 会议记录 (Ed. C. Ding, T. Helleseth, 和 H. Niederreiter). New York: Springer-Verlag, pp. 1-16, 1999.Allouche, J.-P. 和 Shallit, J. "示例 5.1.2 (Thue-Morse 序列)." 自动序列：理论、应用、推广。 Cambridge, England: Cambridge University Press, pp. 152-153, 2003.Goldstein, S.; Kelly, K. A.; 和 Speer, E. R. "Thue-Morse 序列稀疏和的分形结构。" J. Number Th. 42, 1-19, 1992.Kindermann, L. "MusiNum--数字中的音乐。" http://reglos.de/musinum/.Lothaire, M. (Ed.). 词语组合学。 Cambridge, England: Cambridge University Press, 1997.Morse, M. "负曲率表面上的循环测地线。" Trans. Amer. Math. Soc. 22, 84-100, 1921.Morse, M. 和 Hedlund, G. A. "无休止的国际象棋，符号动力学和半群问题。" Duke Math. J. 11, 1-7, 1944.Pickover, C. A. "巴布亚的管子。" Ch. 17 在 数字奇观：数学、思维和意义的冒险。 Oxford, England: Oxford University Press, pp. 34-38, 2001.Prouhet, E. "关于数字幂之间的一些关系的备忘录。" C. R. Adad. Sci. Paris Sér. 1 33, 225, 1851.Robbins, D. "问题 E2692 的解答。" Amer. Math. Monthly 86, 394-395, 1979.Schroeder, M. R. 分形、混沌和幂律：来自无限天堂的时刻。 New York: W. H. Freeman, 1991.Sloane, N. J. A. 序列 A010060 和 A048707 在 "整数序列在线百科全书" 中。Sondow, J. "问题 11222。" Amer. Math. Monthly 113, 459, 2006.Thue, A. "关于无限符号序列。" Norske vid. Selsk. Skr. Mat. Nat. Kl. 7, 1-22, 1906. 重印于 Axel Thue 的精选数学论文 (Ed. T. Nagell). Oslo: Universitetsforlaget, pp. 139-158, 1977.Thue, A. "关于某些符号序列的相同部分的相互位置。" Norske vid. Selsk. Skr. Mat. Nat. Kl. 1, 1-67, 1912. 重印于 Axel Thue 的精选数学论文 (Ed. T. Nagell). Oslo: Universitetsforlaget, pp. 413-478, 1977.Wolfram, S. 一种新的科学。 Champaign, IL: Wolfram Media, pp. 890 和 1092, 2002.Woods, D. R. "问题提案 E2692。" Amer. Math. Monthly 85, 48, 1978.

在 Wolfram|Alpha 上引用

Thue-Morse 序列

请引用为

Weisstein, Eric W. "Thue-Morse 序列。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Thue-MorseSequence.html

主题分类