紙對摺時產生的凹凸痕迹的規律，能否用公式表達？

12-02

對摺一次是…凹
兩次…凹凹凸
三次…凹凹凸凹凹凸凸

這個問題挺好玩的。

題主可以做一個實驗：拿一根紙帶，不斷地對摺，然後把每一處摺痕按原來的凹凸展開成直角：

（圖片來自維基百科）

這樣就會得到 @新澤西管風琴的答案里那個漂亮的圖案。這個圖案叫做龍曲線（Dragon curve）。

然後，規律是什麼呢？

我們把凹記作1，凸記作-1。只折一次，得到的當然是：

1

折兩次，就會在原來這個1的前面和後面各增加一個摺痕，前面是1，後面是-1（加粗的是原有的摺痕）：

1, 1, -1

折三次，會在折兩次的基礎上，在最前面、最後面和相鄰的兩個摺痕之間，都添上新的摺痕。而且新添上的摺痕會按1、-1、1、-1……這樣的規律排列。也就是說，相鄰的兩個新摺痕的方向是相反的（詳細的解說可以看 @Richard Xu 的回答）：

1, 1, -1, 1, 1, -1, -1

類似地，我們可以得到折四次的結果：

1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1

這裡每一個數列都是後面一個數列的開頭。如果我們無限地折下去的話，可以得到一個無限長的數列：

1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, …

在線整數數列百科（OEIS）里也收錄了這個數列，編號是A034947。

而且，我們不難得到這樣一個遞推公式：

a(2n) = a(n)
a(4n+1) = 1
a(4n+3) = -1

不過，這個數列在OEIS上的名字跟摺痕沒有關係，而是：雅可比（或克羅內克）符號 (-1/n) 。

克羅內克符號是雅可比符號的推廣，雅可比符號又是勒讓德符號的推廣。它們都是數論里重要的函數。

下面我直接引我在果殼發過的一個帖子（#TIL#可以用克羅內克符號來畫龍曲線）：

學過數論的應該都知道勒讓德符號。對於一個整數a和一個素數p，勒讓德符號(a|p)定義為：如
果a≡0 (mod p)，則(a|p)=0；否則，如果存在一個整數x使得x^2≡a (mod
p)，則(a|p)=1；否則(a|p)=-1。總之，就是看a是不是與某個數的的平方模p同餘。勒讓德符號有很多有趣的性質，在數論里十分有用。

勒讓德符號中的p只能是素數。雅可比把它推廣了一下。對於一個正奇數m，如果它的素因數分解是m=p1*p2*…*ps，那麼定義雅可比符號(n/m)=(n|p1)*(n|p2)*…*(n|ps)，其中右邊那一串就是勒讓德符號。

雅可比符號中的m只能是正奇數。於是，克羅內克把它再推廣了一下。他首先補上了m=-1和m=2的情況。對於m=-1的情況，若n&<0，則 (n/-1)=-1；若n&>0，則(n/-1)=1；(0/-1)=0。對於m=2的情況，定義與勒讓德符號不同，n是偶數時，(n
/2)=0；n≡±1 (mod 8)時，(n/2)=1；n≡±3 (mod
8)時，(n/2)=-1。然後，對於一個非0的整數m，如果它的素因數分解是m=u*p1*p2*…*ps，其中u是±1，那麼定義(n/m)=(n
/u)*(n/p1)*(n/p2)*…*(n/ps)。最後，規定(1/0)=(-1/0)=1，對其它的n定義(n/0)=0。

這樣，對所有整數n、m我們都定義了一個(n/m)。這就是克羅內克符號。

（這裡我把這幾個符號橫著寫了，而且為了區分，勒讓德符號用了|，雅可比和克羅內克符號用了/。正式的寫法應該是豎著寫，比如說， $left(frac{a}{p} ight)$ 。）

上面說了一大堆，都是些數論里的東西，好像與分形沒有什麼關係……

我們來看數列(-1/n)，這裡的n取正整數。根據定義不難看出，這個數列裡邊的每一項只能是1或者-1。這是OEIS里的數列A034947，開頭幾項是： 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1 ……

然後，假設你是一隻海龜，每次從數列中讀取一項；如果是1，就向左轉90°，向前爬一步；如果是-1，就向右轉90°，向前爬一步。這樣，畫出來的圖像是什麼？

（原帖中是動圖，知乎不支持。請點這裡查看：http://ww2.sinaimg.cn/mw690/6e53d84fjw1es2fy9vp48g207x0c0hdy.gif）

嗯，就是龍曲線。

再放一張彩圖：

帖子里並沒有說明白克羅內克符號和上面那個數列為什麼會有這樣的關係。這裡補充一下，主要就是兩點：

由克羅內克符號的定義，有(-1/2)=1。因此，(-1/n)=(-1/2n)。
數論里的一個重要的結論，有些書把它叫做二次互反律的補充律：對於奇素數p，當p≡1 (mod 4)時，勒讓德符號(-1|p)=1；當p≡3 (mod 4)時，勒讓德符號(-1|p)=-1。

由這兩點不難得到前面說過的那個遞推公式。

順便說一句，我沒學過logo語言，帖子里的海龜我是用Mathematica畫的，參考了KTurtle的圖標。

注意到，第n+1次新產生的摺痕，是在第n次新產生的摺痕的左側一個「凹」，右側一個「凸」
比如（加粗表示上一次新產生的摺痕，下劃線表示這一次新產生的摺痕）
第1次：凹
第2次：凹凹凸
第3次：凹凹凸凹凹凸凸

原因很簡單，假定原來的紙是分正反面的：
假如第n次產生了一個「凹」，那麼第n次之前「凹」兩側的紙一定是正面朝上，那麼第n次之後，「凹」左邊的紙變成正面朝上，「凹」右邊的紙變成反面朝上，第n+1次之後左邊的紙上就會多一道「凹」，右邊的紙上就會多一道「凸」。
假如第n次產生了一個「凸」，那麼第n次之前「凸」兩側的紙一定是反面朝上，那麼第n次之後，「凸」左邊（觀察者的左邊）的紙是反面朝上，「凸」右邊（觀察者的右邊）的紙是正面朝上，第n+1次之後左邊（觀察者的左邊）的紙上就會多一道「凸」，右邊（觀察者的右邊）的紙上就會多一道「凹」。BUT！因為之前是反面朝上，觀察者的左右和在紙（的正面）上的左右是反的，當我們全部展開之後，仍然是「凸」在紙上的左邊（原來觀察者的右邊）是「凹」，而「凸」在紙上的右邊（原來觀察者的左邊）是「凸」。
（看不懂的請自己折張紙試一下……注意永遠是從右往左折……）

那麼如何表示這種規律呢？
我們假定這是第n次摺紙，我們標記第k個位置為k/2^n，然後將k/2^n化簡為最簡分數p/q，若p模4餘1則第k個位置為「凹」，若p模4餘3則第k個位置為「凸」。
用第3次的作為例子：
1 ==&> 1/8 ==&> 1/8 ==&> 凹
2 ==&> 2/8 ==&> 1/4 ==&> 凹
3 ==&> 3/8 ==&> 3/8 ==&> 凸
4 ==&> 4/8 ==&> 1/2 ==&> 凹
5 ==&> 5/8 ==&> 5/8 ==&> 凹
6 ==&> 6/8 ==&> 3/4 ==&> 凸
7 ==&> 7/8 ==&> 7/8 ==&> 凸
其實這個做法脫胎於下面這個更加「計算機」的做法，我只是把下面這個做法改寫成了和序號相關的做法而已：

構造一棵N層的滿二叉樹，根節點是「凹」，每個左子結點標上「凹」，右子節點標上「凸」，然後做一個中序遍歷即可，如下圖：

Mathematica:
用 f 生成摺痕，然後用 AnglePath 作圖.

f=Mod[Numerator[Range[2^#-1]/2^#],4]-2

ListLinePlot@Prepend[AnglePath[f[12]Pi/2],{-1,0}]

既然最高的票給出了遞推和圖形，我就借花獻佛，上一段python海龜繪圖吧。

import turtle import time


def plot(a):

	turtle.shape("turtle")

	turtle.goto(0,0)

	step=10

	for i in a:

		if i==1:

			turtle.left(90)

			turtle.forward(step)

		else:

			turtle.right(90)

			turtle.forward(step)

	time.sleep(10)
def main():

	n=2000

	a=[1,]*n

	for i in range(n):

		if (i+1)%2==0:

			a[i]=a[i//2]

		else:

			if (i+1)%4==1:

				a[i]=1

			else:

				if (i+1)%4==3:

					a[i]=-1

	plot(a)

if __name__ == "__main__": main()

沒有人說這玩意兒叫d—automate么

受@Richard Xu 啟發，做了一個小程序，複習了遞歸和二叉樹，thx！

如果用1來表示凹痕，-1來表示凸痕，那麼可以表示成：
F(n)=(-1)^m，n=(2m+1)*2^p 。
其中m，p均為自然數。
譬如n=5時，p必須取0，m就為2，F為1，故為第5條為凹痕;
當n=6時，p必須取1，m就為1，F為-1，所以第6條為凸痕。
有趣的是，不論折幾次，該公式似乎都可以適用。

題主可以去關注有種叫做分形的東西。有規則分形和不規則分形，你問的這種屬於規則的，還包括雪花等。像海岸線，股市等就屬於不規則的