昌小澤的秘密基地

雖然因為當兵而錯過了 3 月 12 日
但本部落格一年一度慶祝「植樹節」的活動並不會因此而暫停
沒錯!! 我們又要來關心是否有新的「梅仙涅質數 (Mersenne prime)」再被找出
而今年恰逢本活動的第五週年 所以先來個特別企劃
讓我們先來認識一下 到底什麼是梅仙涅質數

所謂的「梅仙涅質數 (Mersenne prime)」指得是型如
2ⁿ - 1 的質數 其中 n 也是質數
他有什麼特別的地方呢? 如果你有興趣的話可以試試看
n = 2 時 2² - 1 = 3 (質數)
n = 3 時 2³ - 1 = 7 (質數)
n = 5 時 2⁵ - 1 = 31 (質數)
n = 7 時 2⁷ - 1 = 127 (質數)
但到了 n = 11 時
2¹¹ - 1 = 2047 = 23 x 89 卻不是個質數
照理說故事到這裡就要停住
不過呢...
(n = 13) 2¹³ - 1 = 8191, (n = 17) 2¹⁷ - 1 = 131071, (n = 19) 2¹⁹ - 1 = 524287 卻都是質數
所以說 我們可以大膽的猜測
或許只有少數的質數 (例如 11) 無法讓 2ⁿ - 1 不是質數
這樣的猜測 讓很多數學家為之瘋狂 開始"撩"下去尋找

注意一件事 這個時候大約是 16 - 17 世紀
要判斷一個數是不是質數 這是一個很難的事情
所以不要把上面的工作想的太簡單
而且 說實在話 因為計算量太大 因而產生了很多的錯誤
這些錯誤一直要到 19 世紀才陸陸續續的被更正過來

我們的主角要出現了
梅仙涅 (Marin Mersenne 1588-1648) 在 1644 年於他的書中聲稱
當 n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 與 257 時
2ⁿ - 1 一定會是質數
而且其他比 257 還要小的質數 n 都無法使 2ⁿ - 1 成為質數 先不管他的聲稱是否正確 (實際上錯誤百出) 2²⁵⁷ - 1 有多大 你知道嗎?
它是一個 78 位數的數字!!
寫起來會像這樣 (by Windows 小算盤)
23158417847463239084714197001738xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 光是把這個數字確切的寫出來都很困難了 更別說還要檢驗他是不是質數
因此 我們就把這個榮耀給了梅仙涅
如果 2ⁿ - 1 是一個質數 則我們把這個質數稱為「梅仙涅質數 (Mersenne prime)」

好 我們先更正一下梅仙涅的錯誤 而這個更正一直到 1947 年才被完成
(由此你也可以看出他有多大膽 與 多閒 XD 不是啦 是多麼的狂熱)
在小於 258 的所有質數中 只有
n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 與 127 能使 2ⁿ - 1 成為質數

之後還是陸陸續續的有人繼續在尋找後面的梅仙涅質數
只是可想而知 這並不是件容易的事情
一來 梅仙涅質數並不如我們一開始所想像的那麼多
或可以說「稀少」
像 127 之後要到 521 才又是梅仙涅質數
再來就是數字越來越大
像 2⁵²¹ - 1 就是個 157 位數!!
所以必須得說 敢挑戰的人真的是很有勇氣

近幾年 因為電腦的發展
找梅仙涅質數這個繁重的工作 就交給了電腦處理
1996 年 因為網路的發達
因而有人想到 將大家電腦閒置的 CPU 利用網路的串連 形成一台超級大電腦
來繼續尋找梅仙涅質數
因而出現了 GIMPS (Great Internet Mersenne Prime Search) 這個網路組織
以平均每年可以找到一個梅仙涅質數的速度 繼續拓展著梅仙涅質數的數量

好 重點來了 今年的梅仙涅質數的尋找 是否有了新的進展呢?
首先 是去年的延續
去年有提到 EEF (Electronic Frontier Foundation) 有提供一筆獎金 (10 萬美金)
給第一個發現「超過一千萬位」質數 (不一定要是梅仙涅質數) 的人
(這就是網路的力量啊... 10,000,000 位數的數字 這用人工來算絕對會死人的!!)
而去年 GIMPS 一連發現兩個超過一千萬位的梅仙涅質數:
2^37156667 - 1 (11185272位數) 與 2^43112609 - 1 (12978189位數) 因此在確認過後 於 2009 年 10 月 22 日把這個獎金頒給了 GIMPS
而 GIMPS 下一個目標 應該就是可以得到 15 萬美金的「一億位數」吧 ^^

好 那接下來的狀況呢?
對我們來說是件開心的事 因為又有新的梅仙涅質數出現了
但對 GIMPS 來說可能沒有太開心 因為他屆於上述兩數之間 沒有繼續拓展位數

在 2009 年 4 月 12 日 GIMPS 發現了第 47 個梅仙涅質數 (但就大小來說 是第 46 個)
M(42643801) = 2^42643801 - 1 這是一個 12,837,064 位數的質數 比之前發現的 M(43112609) 還要小
再次的發生了逆轉的情況 (M(37156667) 也是比他晚找到 詳見去年的文章)
至於還會不會再逆轉? 這後面再來說

除了尋找新的質數外 GIMPS 也是會檢查是不是有漏網之魚
根據 GIMPS 網站上的資料
2009 年 4 月 8 日 把 n = 25964951 之前的質數都檢查過至少一遍
而 M(25964951) 是在 2005 年所發現的第 42 個梅仙涅質數 計有 7,816,230 位數
所以 到目前為止 我們只能確定前 42 個梅仙涅質數是正確的 而且就只有這 42 個
但之後的 就還得繼續驗證下去才知道
所以呢 你說會不會再找到比現在已知的梅仙涅質數還要小的梅仙涅質數
這真的還很難說 就看看這新的一年會有怎樣的發展囉 ^^

相關連結:
- Mersenne Primes: History, Theorems and Lists
　[有梅仙涅質數的介紹 歷代發現者與相關的資訊 開頭的介紹即是參考於此]
- GIMPS (Great Internet Mersenne Primes Search)
　[找尋梅仙涅質數的網路組織 你也可以加入喔]
- EFF Cooperative Computing Awards
　[文章中提到提供獎金的組織]

延伸閱讀:
- 2009年的植樹節談「質數」
　[有 M(37156667) 與 M(43112609), 目前第 45 與 47 個梅仙涅質數的介紹]
- 2008年的植樹節談「質數」 [沒有任何新發現]
- 2007年的植樹節談「質數」 [有 M(32582657), 目前的第 44 個梅仙涅質數的介紹]
- 2006年的植樹節談「質數」 [有 M(30402457), 目前的第 43 個梅仙涅質數的介紹]