跳至內容

皮薩諾週期

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數論中,自然數 n 的皮薩諾週期(通常記為π(n))是斐波那契數列n 後的週期,以意大利數學家萊昂納多·皮薩諾(即斐波那契)的名字命名。斐波那契數列取模後,週期的存在性曾在1774年為約瑟夫·拉格朗日所提及。[1][2]

定義

斐波那契數列是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... (OEIS數列A000045

斐波那契數列由下方的遞歸關係定義

對於任意整數n, 數列{Fi (mod n)}為週期數列。皮薩諾週期π(n)記為該數列的週期。例如,模3的斐波那契數列前若干項為:

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ... (OEIS數列A082115

這一數列以8為週期,故π(3) = 8.

性質

除去π(2) = 3 以外,皮薩諾週期必為偶數。這一性質的一個簡單證明可由如下事實導出:

考慮斐波那契矩陣

則π(n)應等同於矩陣 在一般線性群GL2(ℤn)的階,其中GL2(ℤn)表示在整數模 環上全體二階可逆矩陣構成的乘法群。由於F的行列式為−1, 可知在ℤn中有(−1)π(n) = 1, 故π(n)為偶數。[3]

m,n 互質時,由中國剩餘定理即知π(mn)等於π(m)和π(n)的最小公倍數。例如,π(3) = 8 而π(4) = 6,由此可得π(12) = 24. 因此,對皮薩諾週期的研究可以化歸為對質數冪q = pk (k ≥ 1) 的皮薩諾週期的研究。

可以證明,若p為質數,則π(pk)整除pk–1π(p). 有猜想認為對一切質數p及整數k > 1成立。任何不滿足該猜想的質數p都必然是一個沃爾-孫-孫質數,而這種質數被猜想並不存在。

因此對皮薩諾週期的研究可以被進一步化歸為對質數的皮薩諾週期的研究。出於這種考慮,需要特別指出兩個反常的質數。質數2的皮薩諾週期為奇數,而質數5的皮薩諾週期和其他質數相比「大得多」。這兩個質數的冪的皮薩諾週期為:

  • n = 2k, 則 π(n) = 3·2k–1 = 3n/2.
  • n = 5k, 則 π(n) = 4·5k = 4n.

由此可知對n = 2·5kπ(n) = 6n.

2和5以外的所有質數均屬於共軛類. 在這一情況下,在模p下由比內公式的類比可知π(p) 是 x2x – 1 的根模p的指數。當時,根據二次互反律,這兩個根在  中,由費馬小定理可知π(p)整除p – 1. 例如,π(11) = 11 – 1 = 10,π(29) = (29 – 1)/2 = 14.

根據二次互反律,x2x – 1 的根不在內,而是在有限體

中。注意到弗比尼斯自同態  將方程的兩根rs交換,因而rp = s,rp+1 = –1. 由此可得r2(p+1) = 1, 故r的階,也即π(p),是2(p+1)除以某個奇數的商,因而必為4的倍數。在這種情況中,最小的三個滿足 π(p)<2(p+1) 的例子為π(47) = 2(47 + 1)/3 = 32, π(107) = 2(107 + 1)/3 = 72 及π(113) = 2(113 + 1)/3 = 76.

據上述討論,若n = pk是一個奇質數冪,滿足π(n) > n, 則 π(n)/4 是一個不大於n的整數。利用皮薩諾週期的乘積性質,可得

π(n) ≤ 6n,

等號成立當且僅當n = 2 · 5r, r ≥ 1. 最小的兩個等號成立的例子為 π(10) = 60 及 π(50) = 300. 若 n 不能表示為 2 · 5r 的形式,則π(n) ≤ 4n.

列表

前十二個自然數的皮薩諾週期(OEIS中的數列A001175)及其對應的一個週期內的所有數列舉如下(為可讀性起見,在每個0前加有空格;X, E分別表示10, 11):[4]

n π(n) 一個週期中0的數目 (OEISA001176) 一個週期中的所有數(OEISA161553) OEIS
1 1 1 0 A000004
2 3 1 011 A011655
3 8 2 0112 0221 A082115
4 6 1 011231 A079343
5 20 4 01123 03314 04432 02241 A082116
6 24 2 011235213415 055431453251 A082117
7 16 2 01123516 06654261 A105870
8 12 2 011235 055271 A079344
9 24 2 011235843718 088764156281 A007887
10 60 4 011235831459437 077415617853819 099875279651673 033695493257291 A003893
11 10 1 01123582X1 A105955
12 24 2 011235819X75 055X314592E1 A089911
π(n) +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12
0+ 1 3 8 6 20 24 16 12 24 60 10 24
12+ 28 48 40 24 36 24 18 60 16 30 48 24
24+ 100 84 72 48 14 120 30 48 40 36 80 24
36+ 76 18 56 60 40 48 88 30 120 48 32 24
48+ 112 300 72 84 108 72 20 48 72 42 58 120
60+ 60 30 48 96 140 120 136 36 48 240 70 24
72+ 148 228 200 18 80 168 78 120 216 120 168 48
84+ 180 264 56 60 44 120 112 48 120 96 180 48
96+ 196 336 120 300 50 72 208 84 80 108 72 72
108+ 108 60 152 48 76 72 240 42 168 174 144 120
120+ 110 60 40 30 500 48 256 192 88 420 130 120
132+ 144 408 360 36 276 48 46 240 32 210 140 24

斐波那契數的皮薩諾週期

如果n = F (2k) (k ≥ 2), 那麼π(n) = 4k; 如果n = F (2k + 1) (k ≥ 2), 那麼π(n) = 8k + 4. 換而言之,模 F(2k) (k ≥ 2)的一個週期內有兩個0,而模F (2k + 1) (k ≥ 2)的一個週期內有四個0.

k F (k) π(F (k)) 截至首個0出現前的一個(對 k ≤ 3)或一半(對不小於4的偶數k)、四分之一個(對不小於4的奇數k)週期
1 1 1 0
2 1 1 0
3 2 3 0, 1, 1
4 3 8 0, 1, 1, 2
5 5 20 0, 1, 1, 2, 3
6 8 12 0, 1, 1, 2, 3, 5
7 13 28 0, 1, 1, 2, 3, 5, 8
8 21 16 0, 1, 1, 2, 3, 5, 8, 13
9 34 36 0, 1, 1, 2, 3, 5, 8, 13, 21
10 55 20 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
11 89 44 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
12 144 24 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
13 233 52 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14 377 28 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15 610 60 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16 987 32 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17 1597 68 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18 2584 36 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19 4181 76 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20 6765 40 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21 10946 84 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22 17711 44 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23 28657 92 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24 46368 48 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

參考文獻

  1. ^ Weisstein, Eric W., "Pisano Period"頁面存檔備份,存於互聯網檔案館), MathWorld.
  2. ^ On Arithmetical functions related to the Fibonacci numbers頁面存檔備份,存於互聯網檔案館).
  3. ^ A Theorem on Modular Fibonacci Periodicity頁面存檔備份,存於互聯網檔案館).
  4. ^ Graph of the cycles modulo 1 to 24.