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