千萬不要迷信規(guī)律——大反例合集(編輯修改稿)
2025-08-31 14:35 本頁面
【文章內(nèi)容簡介】 60。事實(shí)上，根據(jù) Fermat 小定理，如果 p 是素數(shù)，那么 p 一定能整除 2n 2。不過，它的逆定理卻是不成立的，上面提到的 341 便是一例。我們把這種數(shù)叫做以 2 為底的偽素數(shù)。由于這種素數(shù)判定法的反例出人意料的少，我們完全可以用它來做一個概率型的素數(shù)判定算法。事實(shí)上，著名的 MillerRabin 素性測試算法就是用的這個原理。Perrin 偽素數(shù)定義 f(n) = f(n 2) + f(n 3) ，其中 f(1) = 0 ， f(2) = 2 ， f(3) = 3 。這個數(shù)列叫做 Perrin 數(shù)列。似乎有這么一個規(guī)律： n 能整除 Perrin 數(shù)列的第 n 項(xiàng) f(n) ，當(dāng)且僅當(dāng) n 是一個素數(shù)。如果這個規(guī)律成立的話，我們也將獲得一個效率非常高的素數(shù)檢驗(yàn)方法。根據(jù) MathWorld 的描述，1899 年 Perrin 本人曾經(jīng)做過試驗(yàn)，隨后 Malo 在 1900 年， Escot 在 1901 年，以及 Jarden 在 1966 年都做過搜索，均未發(fā)現(xiàn)任何反例。直到 1982 年， Adams 和 Shanks 才發(fā)現(xiàn)第一個反例 n = 271 441 ，它等于 521 521 ，卻也能整除 f(271 441) 。下一個反例則發(fā)生在 n = 904 631 的時候，再下一個反例則是 n = 16 532 714 。這種反例被稱為 Perrin 偽素數(shù)。最經(jīng)典的大反例說到大反例，這是我最喜歡舉的例子。下面是大于 1 的正整數(shù)分解質(zhì)因數(shù)后的結(jié)果：2 = 23 = 34 = 2 25 = 56 = 2 37 = 78 = 2 2 29 = 3 310 = 2 5...其中，10 包含偶數(shù)個質(zhì)因子，其余的數(shù)都包含奇數(shù)個質(zhì)因子。你會發(fā)現(xiàn)，在上面的列表中一行一行地看下來，不管看到什么位置，包含奇數(shù)個質(zhì)因子的數(shù)都要多一些。1919 年，George P243。lya 猜想，質(zhì)因子個數(shù)為奇數(shù)的情況不會少于 50% 。也就是說，對于任意一個大于 1 的自然數(shù) n ，從 2 到 n 的數(shù)中有奇數(shù)個質(zhì)因子的數(shù)不少于有偶數(shù)個質(zhì)因子的數(shù)。
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1