0


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→+∞lim​Fn+1​Fn​​=25​−1​

一、生成斐波拉契数列

按照递推公式即可写出如下代码:

deffibonacci(n):
    a, b =0,1for i inrange(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 =0for k inrange(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 +=1break

输出结果如下:

[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)//2for k inrange(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]))}')iflen(lst[0:k])==2*i+2:print(f'最小正周期等于 2p+2','\n')
                lst_1.append(i)
                u +=1eliflen(lst[0:k])==i-1:print(f'最小正周期等于 p-1','\n')
                lst_2.append(i)
                r +=1else:print('\n')
            s +=1breakprint(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 吧 !

标签: python 算法

本文转载自: https://blog.csdn.net/weixin_43817941/article/details/126558108
版权归原作者 Travis Wang 所有, 如有侵权,请联系我们删除。

“Python 探讨斐波拉契数列模素数的周期问题”的评论:

还没有评论