Regular paperfolding sequence

hbghlyj

Regular paperfolding sequence定义为以下0-1序列的极限:

1

1 1 0

1 1 0 1 1 0 0

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0

每次将前一个序列的项,插入一个 1,0,1,0⋯ 的交替序列。从 $n = 1$ 开始，Regular paperfolding sequence的前几项是：
1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (sequence A014577 in the OEIS)

hbghlyj

在regular paperfolding sequence中任何给定项 $t_n$ 的值可以递归地计算如下。如果 $n = m·2^k$ 其中 $m$ 是奇数，则 ${\displaystyle t_{n}={\begin{cases}1&{\text{if }}m\equiv 1\mod 4\\0&{\text{if }}m\equiv 3\mod 4\end{cases}}}$

所以 t₁₂ = t₃ = 0 但 t₁₃ = 1.

The paperfolding word 1101100111001001... 是通过连接regular paperfolding sequence的项获得的，是以下态射(morphism)或字符串替换规则的不动点

11 → 1101

01 → 1001

10 → 1100

00 → 1000

像下面这样:

11 → 1101 → 11011001 → 1101100111001001 → 11011001110010011101100011001001 ...

从态射规则可以看出，paperfolding word最多包含三个连续的 0，最多包含三个连续的 1。
paperfolding sequence也满足对称关系：
${\displaystyle t_{n}={\begin{cases}1&{\text{if }}n=2^{k}\\1-t_{2^{k}-n}&{\text{if }}2^{k-1}< n<2^{k}\end{cases}}}$
这表明paperfolding word为另一个迭代过程的极限，如下所示：

1

1 1 0

110 1 100

1101100 1 1100100

110110011100100 1 110110001100100

在每次迭代中，将 1 放置在前一次迭代字符串的末尾，然后以相反的顺序重复此字符串，将 0 替换为 1，1 替换为 0。

hbghlyj

由构造过程知paperfolding sequence的生成函数${\displaystyle G(t_{n};x)=\sum _{n=1}^{\infty }t_{n}x^{n}}$满足
${\displaystyle G(t_{n};x)=G(t_{n};x^{2})+\sum _{n=0}^{\infty }x^{4n+1}=G(t_{n};x^{2})+{\frac {x}{1-x^{4}}}\,.}$