皮萨诺周期

数论当中,自然数 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的数目 ( A001176) 一个周期中的所有数( A161553) 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.