如果你问一个搞数学的人把“斐波那契”和“素数”放在一起能玩出什么来他大概率会眼睛一亮。这两个概念一个是兔子生小兔生出来的数列一个是从欧几里得时代就被反复琢磨的“数论原子”表面上看八竿子打不着放到一起之后却藏着不少让人上头的冷知识。这篇文章算是我自己把这两个东西揉在一起折腾时的一些记录和思考不是教科书更不是劝退式的论文而是那些“我试过、我算过、我踩过坑”的真实笔记。适合对数字有点好奇、喜欢抠细节的朋友也适合准备做数学科普、竞赛辅导或是单纯想写个小程序玩一玩的人。我会先从斐波那契和素数的基本盘讲起再慢慢拆开它们到底在哪里交汇最后给出完整可跑的代码和验证过程。整个思路比较长但每段都能“抄作业”你跟着走一遍会发现这两个概念远比想象中有意思。1. 斐波那契从一对兔子开始的数列1.1 兔子问题的原始设定和它引出的递推关系斐波那契数列的故事大家多少都听过假设有一对刚出生的小兔子一个月后成熟再过一个月开始生育之后每个月都生一对新的兔子而且兔子永远不死问一年后一共有多少对兔子为了简化斐波那契把“兔子生小兔”的概率问题全部抹平得到的是一串非常干净的数字1, 1, 2, 3, 5, 8, 13, 21……这个数列的规则简单到令人发指每一项等于前两项之和。写成递推公式就是F(1)1F(2)1F(n)F(n-1)F(n-2)。我每次给学生讲到这里都会强调这个递推关系才是斐波那契真正的“魂”。兔子故事只是个壳递推关系决定了它后续所有让人惊呼的性质。你换个场景比如“细菌分裂”“细胞复制”“爬楼梯”只要满足同样的叠加规则得到的都是同一串数字这说明数学规律和具体故事无关它抓的是结构。1.2 黄金分割斐波那契为什么与1.618形影不离把斐波那契相邻两项的比值列出来1/112/123/21.55/3≈1.6678/51.613/81.62521/13≈1.615……随着项数增加这个比值会越来越贴近一个固定的数1.6180339887498948482……也就是黄金分割比φ。为什么必然是这个值把这个比值写成极限利用递推关系就能推出 φ 1 1/φ化简成 φ² φ 1解出来就是 (1√5)/2。我试过用程序验算第20项的比值跟φ的误差已经小到10的负8次方级别。这里真正有意思的是一个只涉及自然数和加法的数列极限里居然跳出个带根号5的无理数数学的“跳跃感”在这件事上体现得淋漓尽致。1.3 通项公式根号5是如何钻进整数数列的更反直觉的是这样一个只依赖加法的整数数列居然存在一个用无理数表达的封闭公式叫做比内公式F(n) [φⁿ - (-1/φ)ⁿ] / √5。我第一次见到这个公式时有点懵输出的每一项都是整数公式里却充满了无理数。但展开算几项所有含√5的部分互相抵消剩下的恰好是整数。这个结构跟二项式展开有关核心原因是φ和-1/φ是特征方程x²x1的两个根它们天然对称。实际写代码时我并不推荐用比内公式直接算大数因为浮点数精度会坑人第70项之后误差就开始明显了。真要算大项用矩阵快速幂或者记忆化递归更稳。我会在后面实操部分专门说这件事。1.4 一个有趣的“面积谜题”聊点轻松的东西。斐波那契还能拿来变魔术取一个边长为8的正方形面积64。按照5和3的分割切一刀再重新拼成一个5×13的长方形面积却是65。多出来的1个单位面积到底从哪冒出来的实际上拼接处并不是真正的直线切分的倾斜角差了一点点肉眼看不出来但面积差就藏在这个极细的缝隙里。这个谜题的效果高度依赖斐波那契的性质8×864和5×1365之间差1正对应着斐波那契数之间的卡西尼恒等式F(n)² - F(n-1)F(n1) (-1)^(n-1)。这个恒等式用递推关系几步就能证完但它解释了一大批“切割重拼面积增加”的视觉魔术数学和表演在这儿产生了奇妙的交点。2. 素数数论里的“原子”与分布之谜2.1 素数为什么重要算术基本定理素数定义为大于1且只能被1和自身整除的自然数2, 3, 5, 7, 11, 13……在整数世界素数就像物质世界的化学元素任何大于1的整数都能唯一分解成素数的乘积比如602²×3×5这个唯一分解性就是算术基本定理。我个人的理解是素数并不是“不能被分解的残渣”而是“构成整数的原子”。很多整数问题的核心其实质是素数如何分布、如何组合的问题。举例来说判断一个数是否为素数本质上是在问它“还能不能拆”而把一个数完全拆开拆到不可再拆拆出来的砖块就是素数。2.2 最简单的素数判定为什么只需要试除到平方根判断一个数n是不是素数最朴素的办法是从2一直试到n-1看有没有能整除的这叫试除法。但稍微琢磨一下就知道完全没必要试那么远只要试到√n就够了。理由非常简单如果nab并且a和b都大于√n那么ab就会大于n矛盾。所以如果n是合数那么一定存在一个因子不超过√n。比如判断97是不是素数只需要试除2到9之间的数就行因为√97≈9.85超过9的因子会跟小于9的因子成对出现。这个优化能把效率从O(n)降到O(√n)是后续所有素性算法的基础。2.3 素数到底有多少欧几里得与无穷性素数有无穷多个吗有。欧几里得给出了一个极其优雅的证明假设素数是有限的把它们全部乘起来再加1得到的新数要么本身是素数要么有一个新的素因子不管哪种情况都跟“全部素数”的假设矛盾。这个证明不需要任何计算分分钟让新手体会到数学的威力。我现实中给学生讲到这里时总有人问“那素数到底密不密”。这个问题引出了数论里最深刻的一条线素数在自然数中的密度以及数量随范围增长的趋势。2.4 素数个数函数与“论小于给定数值的素数个数”记π(x)为不超过x的素数个数。比如π(10)4因为2、3、5、7刚好4个π(100)25。十八世纪末高斯通过大量手工计算猜测π(x)大约等于x除以自然对数x也就是π(x) ≈ x/ln(x)。这个猜测非常准。用数据说话x10^6时π(x)78498而x/ln(x)≈72382误差在8%上下随着x增大这个相对误差会越来越小。为了描述这种“无限接近但永远不太可能完全相等”的关系数学家叫它素数定理直到1896年才被严格证明。这里顺带说一个冷知识“论小于给定数值的素数个数”这句话翻译自黎曼1859年的那篇著名论文标题这篇论文只有短短几页却直接把ζ函数和素数分布拴在了一起进而引出黎曼猜想这个至今悬而未决的大问题。普通人听到“黎曼猜想”以为只是玄学其实它核心还是在回答素数的分布到底有多“乱”有没有隐藏的规律。我个人的态度是理解素数分布最好的起点就是从π(x)和x/ln(x)之间的差值入手它是一切深水区的入口。3. 斐波那契与素数交汇处的冷知识3.1 什么是“斐波那契素数”定义很直白既是斐波那契数又是素数的数。前几项是F(3)2F(4)3F(5)5F(7)13F(11)89F(13)233F(17)1597F(23)28657。看到没有下标是3、4、5、7、11、13、17、23……这里面除了4其它全是素数。这引出一个非常重要的猜想方向除了F(4)3这个特例斐波那契素数的下标很可能全部是素数。为什么会有这个规律用整除性就能解释。斐波那契数列有很强的可整除性如果m能整除n那么F(m)就能整除F(n)。反过来想如果下标n是合数比如nab那F(a)就会是F(n)的因子F(n)就不可能是素数。所以要想F(n)是素数n本身必须具备“避因子”的能力也就是素数。这个逻辑链完整且漂亮是初学者体会整除性的大好素材。3.2 逆命题不成立F(19)418137×113刚才那个规律只说“如果下标是合数那这项不是素数”但没说“下标是素数这项一定就是素数”。逆命题一碰就碎F(19)418137×113。下标19是素数但这项是合数。所以真正寻找斐波那契素数的难度在于即便下标是素数也要逐一去查。目前人类找到的斐波那契素数下标序列一直在增长每一个新发现都意味着巨大的计算量。这种“必要条件容易证、充分条件不存在”的结构在数论里遍地都是也是很多人被它吸引的原因。3.3 卡迈克尔定理与姊妹数列卢卡斯研究斐波那契数列时往往绕不开它的“姊妹数列”卢卡斯数列L(1)1L(2)3L(n)L(n-1)L(n-2)。卢卡斯数列和斐波那契数列共享同样的递推规则只是初值不同。它俩之间存在大量对偶关系比如L(n)²-5F(n)²4(-1)ⁿ这个等式把两个看似不同的序列牢牢绑在一起。我个人做验证时经常用卢卡斯数列来交叉检查斐波那契计算的正确性比单算一遍直观得多。另外还有一个卡迈克尔定理说的是斐波那契数列里绝大多数项都至少有一个新的素因子不会只由之前出现过的素因子反复组成。这个定理我很喜欢因为它展示出“一个看起来简单的递推数列居然能不断产生前所未有的新素数”。这种“常新”的感觉在整数运算里并不常见。3.4 Wall-Sun-Sun素数一个至今未解的存在性问题再往深走一步就是Wall-Sun-Sun素数问题。它定义在斐波那契数列整除性和二次剩余的交界处。如果存在某个素数p让斐波那契数列在模p时出现某类特殊的周期分裂就称它是Wall-Sun-Sun素数。这个问题的核心在于到现在为止人类还不知道它究竟存不存在只是通过大规模计算把搜索范围推到了极深的区域依然一无所获。每次做这类话题时我都会提醒自己数学里的“不知道”有时候比“知道”更有价值它能告诉我们现有工具离真相还有多远。4. 实操用Python把斐波那契和素数抓在一起4.1 前置准备写一个不依赖现成库的素性判断做这个项目不需要装任何第三方库Python自带的整型就能做大整数运算。先写一个基础试除判断def is_prime(n): if n 2: return False if n 2: return True if n % 2 0: return False i 3 while i * i n: if n % i 0: return False i 2 return True这里步长设为2只查奇数效率直接翻倍。实测下来对于100万以内的数这个函数基本秒回对于10位数也能在可接受时间内完成判断。更大的数就不是试除能搞定的了得上Miller-Rabin一类的概率算法这个后面会说。4.2 生成斐波那契数列记忆化递归 vs 迭代 vs 快速倍增斐波那契生成方式非常多。最直观的是递归但纯递归会重复计算大量子问题F(40)就会卡到怀疑人生。所以要么用迭代要么用记忆化。from functools import lru_cache lru_cache(maxsizeNone) def fib_rec(n): if n 2: return 1 return fib_rec(n-1) fib_rec(n-2) def fib_iter(n): a, b 0, 1 for _ in range(n): a, b b, a b return a def fib_fast(n): if n 0: return 0 if n 1: return 1 def _fib(k): if k 0: return (0, 1) a, b _fib(k // 2) c a * (b * 2 - a) d a * a b * b if k % 2 0: return (c, d) else: return (d, c d) return _fib(n)[0]快速倍增的核心思想是已知F(k)和F(k1)可以直接推出F(2k)和F(2k1)。这样算F(100万)只需要几十次递归调用复杂度和log n成正比。我第一次跑快速倍增的时候F(1000000)秒出回看普通迭代要跑一百万个循环差距立刻就出来了。4.3 找到“既是斐波那契又是素数”的数现在把两个函数接起来往下扫描斐波那契数列筛出其中的素数results [] for n in range(3, 200): f fib_iter(n) if is_prime(f): results.append((n, f)) print(n, f)我实测跑到下标200能筛出的斐波那契素数有下标n斐波那契数F(n)32435571311891323317159723286572951422943433494437472971215073从数据上也能看出斐波那契素数高度稀疏而且越到后面越罕见。下标47之后我一直试到200没有再出现新的。这里你会发现现实就是如此规律好写真的掏数据时只有零星几个“幸运儿”。4.4 验证“下标为合数时斐波那契数必为合数”前面说过这个整除性可以直接在代码里验证for n in range(4, 60): if not is_prime(n): f_n fib_iter(n) if is_prime(f_n): print(反例, n, f_n)我运行后没有输出任何内容说明在n4到59的范围内合数下标对应的斐波那契数全部是合数。这个规律非常稳定本质原因就是上面提到的“若m整除n则F(m)整除F(n)”。实际编写时注意F(4)3是唯一的特例只要把n4单独拎出来剩下的结论相当干净。4.5 验证素数个数函数π(x)与x/ln(x)再来算一下素数定理的数值表现。写一个小程序统计不超过x的素数个数并跟x/ln(x)做对比import math def count_primes_up_to(limit): sieve [True] * (limit 1) sieve[0] sieve[1] False for i in range(2, int(limit**0.5) 1): if sieve[i]: for j in range(i*i, limit1, i): sieve[j] False return sum(sieve) for x in [10**3, 10**4, 10**5, 10**6]: pi count_primes_up_to(x) approx x / math.log(x) print(fx{x}, π(x){pi}, x/ln(x){approx:.2f}, 误差{approx/pi:.3%})我跑的典型输出是xπ(x)x/ln(x)相对误差1000168144.766.5%1000012291085.745.4%10000095928685.894.6%10000007849872382.414.2%误差确实在慢慢变小而且趋势稳定。再次强调这个“逼近”并不是单调的会有反复但总体上越来越近这就是素数定理的直观意义。如果只看π(x)和x/ln(x)的比值会发现它无限趋近于1这是另外一个更精确的表述。5. 常见问题与排查实录5.1 为什么我用比内公式算出来的斐波那契数后面就不对了比内公式写着漂亮但实际算到50项左右浮点数精度就开始捣乱。根号5是无理数浮点数只能存到有限位算大整数时会四舍五入出错。我的建议是如果只是为了算F(n)永远用整数递推或者快速倍增不要在素性判断里用浮点。素性判断要求的是绝对精确一丁点偏差都会让你把一个合数当成素数非常致命。5.2 下标从0开始还是从1开始不同资料对F(0)的定义不同。有些书定义F(0)0F(1)1有些定义F(1)1F(2)1。代码和数学公式一旦混用就可能会出现“差一项”的尴尬。我做项目时统一按F(0)0、F(1)1来写程序里的下标和公式完全对应。如果从别处抄来一段代码一定要先确认人家的起点再跟自己的结果比对。5.3 试除法到底能撑到多大的数普通试除法筛到10^7级别很轻松但判断一个像F(1000)那样的几百位数就完全玩不了。这时要上Miller-Rabin概率素性检测Python很多大数库里也默认用它。要知道Miller-Rabin对某些合数存在强伪素数的情况但用它跑多组不同底数错误率会低到实际上可以忽略。我在这个项目里先用小样本试除再用Miller-Rabin做交叉验证两层保险更稳。5.4 不要在“斐波那契素数”搜索里盲目跑大范围我看过网上有些代码直接放n到几百万去搜斐波那契素数结果跑半天没结果。问题不是思路错而是计算量完全失控F(n)本身位数就是指数级增长再对这么巨大的数做素性检测普通机器根本扛不住。想真正突破大记录需要专门设计的高性能算法不是简单把is_prime套上去就行。所以我的建议是把探索范围控制在日常能计算的区域内反而能更快见到规律而不是为了追求大数把自己机器跑死。5.5 警惕“斐波那契解决了黎曼猜想”这类说法我见过不少视频标题用“斐波那契和素数的终极秘密”来吸引眼球点进去什么实质内容都没有。真正有价值的部分反而是上面这些朴素却可验证的小实验。数学科普最忌讳制造神秘感把明明可以用一行代码验证的东西包装成玄学。我的态度是想验证任何关于素数的猜想先跑数据跑不过数据就多想想别急着下结论。结尾的几句个人体会最后分享一点我自己的真实感受把“斐波那契”和“素数”放到一起玩最大的收获不是背下了几个定理名而是亲眼看到“一个简单的递推规则如何反复衍生出不可预测的素数”。我调试代码时最喜欢的场景就是把is_prime套到斐波那契生成器外面等着它一行一行吐结果前几个很快出现之后长时间沉默再突然跳出一个意料之外的素数。那种“等待惊喜”的节奏比任何公式都让人上头。如果你也想复现这个项目我建议从F(200)以内的小范围开始先把基础流程跑通再去挑战更大的下标。过程中遇到任何跟我想法不一样的结果先别急着改代码回头检查一遍递推起点和素性判断的边界条件大概率问题出在这两处。这套玩法本身并不复杂但每一步都踩到真实的数学规律上这就够了。
斐波那契与素数：数学交汇与Python验证实战
如果你问一个搞数学的人把“斐波那契”和“素数”放在一起能玩出什么来他大概率会眼睛一亮。这两个概念一个是兔子生小兔生出来的数列一个是从欧几里得时代就被反复琢磨的“数论原子”表面上看八竿子打不着放到一起之后却藏着不少让人上头的冷知识。这篇文章算是我自己把这两个东西揉在一起折腾时的一些记录和思考不是教科书更不是劝退式的论文而是那些“我试过、我算过、我踩过坑”的真实笔记。适合对数字有点好奇、喜欢抠细节的朋友也适合准备做数学科普、竞赛辅导或是单纯想写个小程序玩一玩的人。我会先从斐波那契和素数的基本盘讲起再慢慢拆开它们到底在哪里交汇最后给出完整可跑的代码和验证过程。整个思路比较长但每段都能“抄作业”你跟着走一遍会发现这两个概念远比想象中有意思。1. 斐波那契从一对兔子开始的数列1.1 兔子问题的原始设定和它引出的递推关系斐波那契数列的故事大家多少都听过假设有一对刚出生的小兔子一个月后成熟再过一个月开始生育之后每个月都生一对新的兔子而且兔子永远不死问一年后一共有多少对兔子为了简化斐波那契把“兔子生小兔”的概率问题全部抹平得到的是一串非常干净的数字1, 1, 2, 3, 5, 8, 13, 21……这个数列的规则简单到令人发指每一项等于前两项之和。写成递推公式就是F(1)1F(2)1F(n)F(n-1)F(n-2)。我每次给学生讲到这里都会强调这个递推关系才是斐波那契真正的“魂”。兔子故事只是个壳递推关系决定了它后续所有让人惊呼的性质。你换个场景比如“细菌分裂”“细胞复制”“爬楼梯”只要满足同样的叠加规则得到的都是同一串数字这说明数学规律和具体故事无关它抓的是结构。1.2 黄金分割斐波那契为什么与1.618形影不离把斐波那契相邻两项的比值列出来1/112/123/21.55/3≈1.6678/51.613/81.62521/13≈1.615……随着项数增加这个比值会越来越贴近一个固定的数1.6180339887498948482……也就是黄金分割比φ。为什么必然是这个值把这个比值写成极限利用递推关系就能推出 φ 1 1/φ化简成 φ² φ 1解出来就是 (1√5)/2。我试过用程序验算第20项的比值跟φ的误差已经小到10的负8次方级别。这里真正有意思的是一个只涉及自然数和加法的数列极限里居然跳出个带根号5的无理数数学的“跳跃感”在这件事上体现得淋漓尽致。1.3 通项公式根号5是如何钻进整数数列的更反直觉的是这样一个只依赖加法的整数数列居然存在一个用无理数表达的封闭公式叫做比内公式F(n) [φⁿ - (-1/φ)ⁿ] / √5。我第一次见到这个公式时有点懵输出的每一项都是整数公式里却充满了无理数。但展开算几项所有含√5的部分互相抵消剩下的恰好是整数。这个结构跟二项式展开有关核心原因是φ和-1/φ是特征方程x²x1的两个根它们天然对称。实际写代码时我并不推荐用比内公式直接算大数因为浮点数精度会坑人第70项之后误差就开始明显了。真要算大项用矩阵快速幂或者记忆化递归更稳。我会在后面实操部分专门说这件事。1.4 一个有趣的“面积谜题”聊点轻松的东西。斐波那契还能拿来变魔术取一个边长为8的正方形面积64。按照5和3的分割切一刀再重新拼成一个5×13的长方形面积却是65。多出来的1个单位面积到底从哪冒出来的实际上拼接处并不是真正的直线切分的倾斜角差了一点点肉眼看不出来但面积差就藏在这个极细的缝隙里。这个谜题的效果高度依赖斐波那契的性质8×864和5×1365之间差1正对应着斐波那契数之间的卡西尼恒等式F(n)² - F(n-1)F(n1) (-1)^(n-1)。这个恒等式用递推关系几步就能证完但它解释了一大批“切割重拼面积增加”的视觉魔术数学和表演在这儿产生了奇妙的交点。2. 素数数论里的“原子”与分布之谜2.1 素数为什么重要算术基本定理素数定义为大于1且只能被1和自身整除的自然数2, 3, 5, 7, 11, 13……在整数世界素数就像物质世界的化学元素任何大于1的整数都能唯一分解成素数的乘积比如602²×3×5这个唯一分解性就是算术基本定理。我个人的理解是素数并不是“不能被分解的残渣”而是“构成整数的原子”。很多整数问题的核心其实质是素数如何分布、如何组合的问题。举例来说判断一个数是否为素数本质上是在问它“还能不能拆”而把一个数完全拆开拆到不可再拆拆出来的砖块就是素数。2.2 最简单的素数判定为什么只需要试除到平方根判断一个数n是不是素数最朴素的办法是从2一直试到n-1看有没有能整除的这叫试除法。但稍微琢磨一下就知道完全没必要试那么远只要试到√n就够了。理由非常简单如果nab并且a和b都大于√n那么ab就会大于n矛盾。所以如果n是合数那么一定存在一个因子不超过√n。比如判断97是不是素数只需要试除2到9之间的数就行因为√97≈9.85超过9的因子会跟小于9的因子成对出现。这个优化能把效率从O(n)降到O(√n)是后续所有素性算法的基础。2.3 素数到底有多少欧几里得与无穷性素数有无穷多个吗有。欧几里得给出了一个极其优雅的证明假设素数是有限的把它们全部乘起来再加1得到的新数要么本身是素数要么有一个新的素因子不管哪种情况都跟“全部素数”的假设矛盾。这个证明不需要任何计算分分钟让新手体会到数学的威力。我现实中给学生讲到这里时总有人问“那素数到底密不密”。这个问题引出了数论里最深刻的一条线素数在自然数中的密度以及数量随范围增长的趋势。2.4 素数个数函数与“论小于给定数值的素数个数”记π(x)为不超过x的素数个数。比如π(10)4因为2、3、5、7刚好4个π(100)25。十八世纪末高斯通过大量手工计算猜测π(x)大约等于x除以自然对数x也就是π(x) ≈ x/ln(x)。这个猜测非常准。用数据说话x10^6时π(x)78498而x/ln(x)≈72382误差在8%上下随着x增大这个相对误差会越来越小。为了描述这种“无限接近但永远不太可能完全相等”的关系数学家叫它素数定理直到1896年才被严格证明。这里顺带说一个冷知识“论小于给定数值的素数个数”这句话翻译自黎曼1859年的那篇著名论文标题这篇论文只有短短几页却直接把ζ函数和素数分布拴在了一起进而引出黎曼猜想这个至今悬而未决的大问题。普通人听到“黎曼猜想”以为只是玄学其实它核心还是在回答素数的分布到底有多“乱”有没有隐藏的规律。我个人的态度是理解素数分布最好的起点就是从π(x)和x/ln(x)之间的差值入手它是一切深水区的入口。3. 斐波那契与素数交汇处的冷知识3.1 什么是“斐波那契素数”定义很直白既是斐波那契数又是素数的数。前几项是F(3)2F(4)3F(5)5F(7)13F(11)89F(13)233F(17)1597F(23)28657。看到没有下标是3、4、5、7、11、13、17、23……这里面除了4其它全是素数。这引出一个非常重要的猜想方向除了F(4)3这个特例斐波那契素数的下标很可能全部是素数。为什么会有这个规律用整除性就能解释。斐波那契数列有很强的可整除性如果m能整除n那么F(m)就能整除F(n)。反过来想如果下标n是合数比如nab那F(a)就会是F(n)的因子F(n)就不可能是素数。所以要想F(n)是素数n本身必须具备“避因子”的能力也就是素数。这个逻辑链完整且漂亮是初学者体会整除性的大好素材。3.2 逆命题不成立F(19)418137×113刚才那个规律只说“如果下标是合数那这项不是素数”但没说“下标是素数这项一定就是素数”。逆命题一碰就碎F(19)418137×113。下标19是素数但这项是合数。所以真正寻找斐波那契素数的难度在于即便下标是素数也要逐一去查。目前人类找到的斐波那契素数下标序列一直在增长每一个新发现都意味着巨大的计算量。这种“必要条件容易证、充分条件不存在”的结构在数论里遍地都是也是很多人被它吸引的原因。3.3 卡迈克尔定理与姊妹数列卢卡斯研究斐波那契数列时往往绕不开它的“姊妹数列”卢卡斯数列L(1)1L(2)3L(n)L(n-1)L(n-2)。卢卡斯数列和斐波那契数列共享同样的递推规则只是初值不同。它俩之间存在大量对偶关系比如L(n)²-5F(n)²4(-1)ⁿ这个等式把两个看似不同的序列牢牢绑在一起。我个人做验证时经常用卢卡斯数列来交叉检查斐波那契计算的正确性比单算一遍直观得多。另外还有一个卡迈克尔定理说的是斐波那契数列里绝大多数项都至少有一个新的素因子不会只由之前出现过的素因子反复组成。这个定理我很喜欢因为它展示出“一个看起来简单的递推数列居然能不断产生前所未有的新素数”。这种“常新”的感觉在整数运算里并不常见。3.4 Wall-Sun-Sun素数一个至今未解的存在性问题再往深走一步就是Wall-Sun-Sun素数问题。它定义在斐波那契数列整除性和二次剩余的交界处。如果存在某个素数p让斐波那契数列在模p时出现某类特殊的周期分裂就称它是Wall-Sun-Sun素数。这个问题的核心在于到现在为止人类还不知道它究竟存不存在只是通过大规模计算把搜索范围推到了极深的区域依然一无所获。每次做这类话题时我都会提醒自己数学里的“不知道”有时候比“知道”更有价值它能告诉我们现有工具离真相还有多远。4. 实操用Python把斐波那契和素数抓在一起4.1 前置准备写一个不依赖现成库的素性判断做这个项目不需要装任何第三方库Python自带的整型就能做大整数运算。先写一个基础试除判断def is_prime(n): if n 2: return False if n 2: return True if n % 2 0: return False i 3 while i * i n: if n % i 0: return False i 2 return True这里步长设为2只查奇数效率直接翻倍。实测下来对于100万以内的数这个函数基本秒回对于10位数也能在可接受时间内完成判断。更大的数就不是试除能搞定的了得上Miller-Rabin一类的概率算法这个后面会说。4.2 生成斐波那契数列记忆化递归 vs 迭代 vs 快速倍增斐波那契生成方式非常多。最直观的是递归但纯递归会重复计算大量子问题F(40)就会卡到怀疑人生。所以要么用迭代要么用记忆化。from functools import lru_cache lru_cache(maxsizeNone) def fib_rec(n): if n 2: return 1 return fib_rec(n-1) fib_rec(n-2) def fib_iter(n): a, b 0, 1 for _ in range(n): a, b b, a b return a def fib_fast(n): if n 0: return 0 if n 1: return 1 def _fib(k): if k 0: return (0, 1) a, b _fib(k // 2) c a * (b * 2 - a) d a * a b * b if k % 2 0: return (c, d) else: return (d, c d) return _fib(n)[0]快速倍增的核心思想是已知F(k)和F(k1)可以直接推出F(2k)和F(2k1)。这样算F(100万)只需要几十次递归调用复杂度和log n成正比。我第一次跑快速倍增的时候F(1000000)秒出回看普通迭代要跑一百万个循环差距立刻就出来了。4.3 找到“既是斐波那契又是素数”的数现在把两个函数接起来往下扫描斐波那契数列筛出其中的素数results [] for n in range(3, 200): f fib_iter(n) if is_prime(f): results.append((n, f)) print(n, f)我实测跑到下标200能筛出的斐波那契素数有下标n斐波那契数F(n)32435571311891323317159723286572951422943433494437472971215073从数据上也能看出斐波那契素数高度稀疏而且越到后面越罕见。下标47之后我一直试到200没有再出现新的。这里你会发现现实就是如此规律好写真的掏数据时只有零星几个“幸运儿”。4.4 验证“下标为合数时斐波那契数必为合数”前面说过这个整除性可以直接在代码里验证for n in range(4, 60): if not is_prime(n): f_n fib_iter(n) if is_prime(f_n): print(反例, n, f_n)我运行后没有输出任何内容说明在n4到59的范围内合数下标对应的斐波那契数全部是合数。这个规律非常稳定本质原因就是上面提到的“若m整除n则F(m)整除F(n)”。实际编写时注意F(4)3是唯一的特例只要把n4单独拎出来剩下的结论相当干净。4.5 验证素数个数函数π(x)与x/ln(x)再来算一下素数定理的数值表现。写一个小程序统计不超过x的素数个数并跟x/ln(x)做对比import math def count_primes_up_to(limit): sieve [True] * (limit 1) sieve[0] sieve[1] False for i in range(2, int(limit**0.5) 1): if sieve[i]: for j in range(i*i, limit1, i): sieve[j] False return sum(sieve) for x in [10**3, 10**4, 10**5, 10**6]: pi count_primes_up_to(x) approx x / math.log(x) print(fx{x}, π(x){pi}, x/ln(x){approx:.2f}, 误差{approx/pi:.3%})我跑的典型输出是xπ(x)x/ln(x)相对误差1000168144.766.5%1000012291085.745.4%10000095928685.894.6%10000007849872382.414.2%误差确实在慢慢变小而且趋势稳定。再次强调这个“逼近”并不是单调的会有反复但总体上越来越近这就是素数定理的直观意义。如果只看π(x)和x/ln(x)的比值会发现它无限趋近于1这是另外一个更精确的表述。5. 常见问题与排查实录5.1 为什么我用比内公式算出来的斐波那契数后面就不对了比内公式写着漂亮但实际算到50项左右浮点数精度就开始捣乱。根号5是无理数浮点数只能存到有限位算大整数时会四舍五入出错。我的建议是如果只是为了算F(n)永远用整数递推或者快速倍增不要在素性判断里用浮点。素性判断要求的是绝对精确一丁点偏差都会让你把一个合数当成素数非常致命。5.2 下标从0开始还是从1开始不同资料对F(0)的定义不同。有些书定义F(0)0F(1)1有些定义F(1)1F(2)1。代码和数学公式一旦混用就可能会出现“差一项”的尴尬。我做项目时统一按F(0)0、F(1)1来写程序里的下标和公式完全对应。如果从别处抄来一段代码一定要先确认人家的起点再跟自己的结果比对。5.3 试除法到底能撑到多大的数普通试除法筛到10^7级别很轻松但判断一个像F(1000)那样的几百位数就完全玩不了。这时要上Miller-Rabin概率素性检测Python很多大数库里也默认用它。要知道Miller-Rabin对某些合数存在强伪素数的情况但用它跑多组不同底数错误率会低到实际上可以忽略。我在这个项目里先用小样本试除再用Miller-Rabin做交叉验证两层保险更稳。5.4 不要在“斐波那契素数”搜索里盲目跑大范围我看过网上有些代码直接放n到几百万去搜斐波那契素数结果跑半天没结果。问题不是思路错而是计算量完全失控F(n)本身位数就是指数级增长再对这么巨大的数做素性检测普通机器根本扛不住。想真正突破大记录需要专门设计的高性能算法不是简单把is_prime套上去就行。所以我的建议是把探索范围控制在日常能计算的区域内反而能更快见到规律而不是为了追求大数把自己机器跑死。5.5 警惕“斐波那契解决了黎曼猜想”这类说法我见过不少视频标题用“斐波那契和素数的终极秘密”来吸引眼球点进去什么实质内容都没有。真正有价值的部分反而是上面这些朴素却可验证的小实验。数学科普最忌讳制造神秘感把明明可以用一行代码验证的东西包装成玄学。我的态度是想验证任何关于素数的猜想先跑数据跑不过数据就多想想别急着下结论。结尾的几句个人体会最后分享一点我自己的真实感受把“斐波那契”和“素数”放到一起玩最大的收获不是背下了几个定理名而是亲眼看到“一个简单的递推规则如何反复衍生出不可预测的素数”。我调试代码时最喜欢的场景就是把is_prime套到斐波那契生成器外面等着它一行一行吐结果前几个很快出现之后长时间沉默再突然跳出一个意料之外的素数。那种“等待惊喜”的节奏比任何公式都让人上头。如果你也想复现这个项目我建议从F(200)以内的小范围开始先把基础流程跑通再去挑战更大的下标。过程中遇到任何跟我想法不一样的结果先别急着改代码回头检查一遍递推起点和素性判断的边界条件大概率问题出在这两处。这套玩法本身并不复杂但每一步都踩到真实的数学规律上这就够了。
