Python 探讨斐波拉契数列模素数的周期问题
Python 探讨斐波拉契数列模素数的周期问题之目录
前言
定义
;
斐波拉契数列又称黄金分割数列，是指数列 1、1、2、3、5、8、13、21、34、55 …，通过递推的方式可准确定义为
F
0
=
0
,
F
1
=
1
,
F
n
=
F
n
−
1
+
F
n
−
2
,
(
n
≥
2
,
n
∈
N
∗
)
F_0=0, ; F_1=1, ; F_n=F_{n-1}+F_{n-2}, ; (n geq 2, n ∈ N^*)
F0=0,F1=1,Fn=Fn−1+Fn−2,(n≥2,n∈N∗)
记
ω
=
1
+
5
2
omega =frac{1+sqrt{5}}{2}
ω=21+5
，
ω
ˉ
=
1
−
5
2
bar{omega} =frac{1-sqrt{5}}{2}
ωˉ=21−5
，则有斐波拉契数列的通项公式：
F
n
=
1
5
(
ω
n
+
ω
ˉ
n
)
F_n = frac{1}{sqrt{5}} left( omega^n + bar{omega}^n right)
Fn=5
1(ωn+ωˉn)
性质
;
斐波拉契数列前一项与后一项之比的极限为黄金分割比，即有
lim
n
→
+
∞
F
n
F
n
+
1
=
5
−
1
2
lim_{n to +infty} frac{F_n}{F_{n+1}} = frac{sqrt{5}-1}{2}
n→+∞limFn+1Fn=25
−1
一、生成斐波拉契数列
按照递推公式即可写出如下代码：
def fibonacci(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
yield a
使用 list(fibonacci(10)) 便输出 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 。
二、创建素数列表
此步方法比较多，大家可以自己发挥，最后使用 primes(20) 要能输出小于
20
20
20 的全体素数 [2, 3, 5, 7, 11, 13, 17, 19] 。本文中至少要求我们能快速生成
10000
10000
10000 以内的素数即可，这是容易实现的，代码不再展示。
三、搜索周期数列的循环节
3.1 斐波拉契数列模
p
p
p 的周期
关于一般周期数列循环节的讨论，原本是比较麻烦的，但由于斐波拉契数列模素数
p
p
p 的周期很有规律，因此可以简单进行编程处理。
首先解释一下循环节的含义，循环节是指周期数列里一个最小正周期里的子数列。比如周期数列 [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, …] 里的循环节为 [1, 2, 3] 。
周期数列的周期往往是指该数列循环节的长度，比如上面的周期数列，其周期为
3
3
3 。
斐波拉契数列模素数
p
p
p 之后形成的新的数列是一个周期数列，我们对于该周期数列的循环节和周期都是十分感兴趣的。
在此，我们给出一个重要结论：
定理
;
设
{
F
n
}
{ F_n }
{Fn} 为斐波拉契数列，
p
p
p 为大于
5
5
5 的素数，数列
F
mathscr{F}
F 为斐波拉契数列
{
F
n
}
{ F_n }
{Fn} 模素数
p
p
p 后的新数列，则当
p
=
1
,
4
m
o
d
5
p = 1, 4 mod 5
p=1,4mod5 时，
F
mathscr{F}
F 的周期为
p
−
1
p-1
p−1 或
p
−
1
p-1
p−1 的因子；当
p
=
2
,
3
m
o
d
5
p = 2, 3 mod 5
p=2,3mod5 时，
F
mathscr{F}
F 的周期为
2
p
+
2
2p+2
2p+2 或
2
p
+
2
2p+2
2p+2 的因子。
上述定理的证明详见论文 The Period of the Fibonacci Sequence Modulo j 中的定理5和定理6。
上述定理告述我们，斐波拉契数列模
p
p
p 的周期最多为
2
p
+
2
2p+2
2p+2 。因此对于模
10000
10000
10000 以内的素数，最大的一个素数为
9973
9973
9973，其周期最多为
19948
19948
19948 。算法仅要求两个周期的匹配即可，故需要至少前
19948
⋅
2
=
39896
19948 cdot 2 = 39896
19948⋅2=39896 个斐波拉契数。本文我们取前
40000
40000
40000 个斐波拉契数，让他们皆模
p
p
p 产生周期数列
F
mathscr{F}
F 。
3.2 循环节的搜寻代码
我们按照上述要求，编写循环节搜寻的 Python 代码：
lstt = [7,1,4,2,8,5,0,7,1,4,2,8,5,0,7,1,4,2]
t = len(lstt)//2
s = 0
for k in range(2, t+1):
if lstt[0:k]==lstt[k:2*k]:
print(lstt[0:k])
print(f'循环节长度为：{len(lstt[0:k])}')
print(f'不同元素个数为：{len(set(lstt[0:k]))}', 'n')
s +=1
break
输出结果如下：
[7, 1, 4, 2, 8, 5, 0]
循环节长度为：7
不同元素个数为：7
3.3 完整实现斐波拉契数列模
p
p
p 循环节
a = primes(10000)
b = list(fibonacci(40000))
s = 0
u = 0
r = 0
lst_1 = []
lst_2 = []
for i in a:
lst = []
for j in b:
lst.append(j % i)
# 计算数列中的循环节
t = len(lst)//2
for k in range(2, t+1):
if lst[0:k]==lst[k:2*k]:
print(lst[0:k])
print(f'循环节长度为：{len(lst[0:k])}')
print(f'p={i} 时循环节的不同元素个数为：{len(set(lst[0:k]))}')
if len(lst[0:k])==2*i+2:
print(f'最小正周期等于 2p+2', 'n')
lst_1.append(i)
u +=1
elif len(lst[0:k])==i-1:
print(f'最小正周期等于 p-1', 'n')
lst_2.append(i)
r +=1
else:
print('n')
s +=1
break
print(f'一共有 {s} 个循环节被输出')
print(f'一共有 {len(a)} 个素数被讨论')
print(f'一共有 {u} 个模数 p 满足最小正周期等于 2p+2')
print(f'满足最小正周期等于 2p+2 的 p 为：{lst_1}')
print(f'一共有 {r} 个模数 p 满足最小正周期等于 p-1')
print(f'满足最小正周期等于 p-1 的 p 为：{lst_2}')
print(f'满足最小正周期等于 2p+2 或 p-1 的占比为：{(u+r)/s}')
我们只挑部分输出如下：
一共有 1229 个素数被讨论
一共有 487 个模数 p 满足最小正周期等于 2p+2
一共有 322 个模数 p 满足最小正周期等于 p-1
满足最小正周期等于 2p+2 或 p-1 的占比为：0.6582587469487388
上述结果表明，还有
420
420
420 个模数
p
p
p 满足周期既不等于
p
−
1
p-1
p−1 又不等于
2
p
+
2
2p+2
2p+2 ，而是它们的某个真因子。
在所有模数里面，
p
=
9349
p=9349
p=9349 是最特殊的一个了，这时斐波拉契数列模
9349
9349
9349 的周期数列的循环节为
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 1597, 8362, 610, 8972, 233, 9205, 89, 9294, 34, 9328, 13, 9341, 5, 9346, 2, 9348, 1, 0] ，
周期仅为
38
38
38 ，在上述周期里只有
28
28
28 个不同的元素，这是令人十分吃惊的！可以说，
9349
9349
9349 是
10000
10000
10000 以内，斐波拉契数列的幸运数字。
四、面向未来的问题
现在我们在此总结出如下五个问题：
问题1
;
若将范围扩大到模
1
,
000
,
000
1,000,000
1,000,000 以内的素数，那么一共有多少个模数
p
p
p 满足周期等于
2
p
+
2
2p+2
2p+2 ？又有多少个模数
p
p
p 满足周期等于
p
−
1
p-1
p−1 ？此时满足周期等于
2
p
+
2
2p+2
2p+2 或
p
−
1
p-1
p−1 的占比为多少 ？
问题2
;
若再将范围扩大到模
100
,
000
,
000
100,000,000
100,000,000 以内的素数，那么一共有多少个模数
p
p
p 满足周期等于
2
p
+
2
2p+2
2p+2 ？又有多少个模数
p
p
p 满足周期等于
p
−
1
p-1
p−1 ？此时满足周期等于
2
p
+
2
2p+2
2p+2 或
p
−
1
p-1
p−1 的占比为多少 ？
问题3
;
考虑模小于
N
N
N 的一切素数，记
C
1
(
N
)
C_1(N)
C1(N) 为满足斐波拉契数列模
p
p
p 的周期等于
2
p
+
2
2p+2
2p+2 的素数
p
p
p 的个数，
C
2
(
N
)
C_2(N)
C2(N) 为满足模
p
p
p 的周期等于
p
−
1
p-1
p−1 的素数
p
p
p 的个数，则下述极限是否存在 ？若存在，又为何值 ？
lim
N
→
+
∞
C
1
(
N
)
+
C
2
(
N
)
π
(
N
)
lim_{N to +infty} frac{C_1(N)+C_2(N)}{pi(N)}
N→+∞limπ(N)C1(N)+C2(N) 其中
π
(
N
)
pi(N)
π(N) 表示小于
N
N
N 的素数个数。
问题4
;
当范围扩大到模
1
,
000
,
000
1,000,000
1,000,000 以内的素数时，对应斐波拉契数列的幸运数字是多少 ？如果范围进一步扩大到
100
,
000
,
000
100,000,000
100,000,000 时，对应斐波拉契数列的幸运数字又是多少 ？
问题5
;
如果范围最后扩大到模全体素数时，是否存在斐波拉契数列的幸运数字 ？若存在，该是什么样的素数呢 ?
以上问题 1、2、4 只需要计算机来完成，问题 3、5 需要严格的数学论证。如果你对计算机感兴趣，那么就去完成问题 1、2、4 ；如果你对数论感兴趣，那么就去尝试完成问题 3、5 吧 ！