問題名字多多

德國數學家考拉茲 (Lother Collatz, 1910-1990)

美國數學家哈塞 (Helmut Hasse 1898-1979)

(照片均取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

 

由 3n+1 說起

「3n+1」問題是這樣的,取一大於一的正整數 n ,其變換方法如下:

若 n 為偶數 (即 n 可被 2 整除) ,則把 n 除以 2, 即 n => n/2;
若 n 為大於 1 的奇數 (即 n 不可被 2 整除) ,則把 n 乘 3 再加 1,再行除以 2。 即 n => (3n+1) / 2。
若 n 為 1 ,則 n 恆為 1 。 即 n => 1。

任何於一的正整數 n ,必定在有限次變換之內,變成 1。

 

例取 n = 2005:

2005 => 3008 => 1504 => 752 => 376 => 188 => 94 => 47 => 71 => 107 =>

161 => 242 => 121 => 182 => 91 => 137 => 206 => 103 => 155 => 233 =>

350 => 175 => 263 => 395 => 593 => 890 => 445 => 668 => 334 => 167 =>

251 => 377 => 566 => 283 => 425 => 638 => 319 => 479 => 719 => 1079 =>

1619 => 2429 => 3644 => 1822 => 911 => 1367 => 2051 => 3077 => 4616 => 2308 =>

1154 => 577 => 866 => 433 =>650 => 325 => 488 => 244 => 122 => 61 =>

92 => 46 => 23 => 35 => 53 => 80 => 40 => 20 => 10 => 5 =>

8 => 4 => 2 => 1 (合共 74 步) 。

若想知道別的數字的路是如何走,或步數多少,可以自己計或到這裡來。

 

問題在我們怎樣稱呼

這問題有一樣東西很特別的,是別名很多。這也是正因為其源起久遠,已難考究之所以。

在二十世紀中葉,開始有很多數學家研究,美國數學普及大師馬丁.加德納 (Martin Gardner 1914 - 2010 ) 把這問題稱為「冰雹猜想」,數字就像夏天雲層中的冰粒,受到氣流的激烈擺布,時而向上,時而向下。日本數學家角谷靜夫 (Shizuo Katutani, 1911 - 2004) 對此問題作過計算,把這問題自歐洲引進日本,更得知此猜想對小於 7*1011 的一切自然數均成立,日本人便稱此問題為「角谷猜想」(Katutani's Conjecture) 。其實在此更早以前,德國格丁根大學 (Georg-August University of Gottingen) 的德國數學家考拉茲 (Lother Collatz, 1910-1990) 和美國數學家哈塞 (Helmut Hasse 1898-1979) 對此問題下了時間,故也有文獻呼之為「考拉茲猜想」 (Collatz Conjecture) 或「哈塞猜想」 (Hasse's Conjecture) 。當然還有一更直接的稱謂,就是「3n+1問題」或「3n+1猜想」(3n + 1 Conjecture) 了。

在 20 世紀的 50 年代,哈塞把這問題帶到美國,角谷靜夫把這問題帶到日本,他們也希望把這問題打垮,可惜未能功成。到了 70 年代,數學界開始出現懸賞:1970年,加拿大數學家考克斯特 (Harold Scott Macdonald Coxeter, 1907 - 2003 ) 獎賞 50 美元,愛爾特希 (Paul Erdos 1913-1996) 把懸賞增加至 500 美元,到了 80 年代,已是 1000 英磅,可惜未有人可把之領取。儘管這猜想未許攻克,但電子計算機對大數的測試,找不到反例 (Counterexample),使我們對此更有信心。數學家大都認為這問題可能與丟番圖逼近 (Diophantine Approximation) 、一致分佈 (Uniform Distribution) 、遍歷理論 (Ergodic Theory)、可計算理論等有密切關係。

 

補充一句,正正因為問題和多人打過交道,問題也有不同的定義,即其變換方法有所不同,如:

若 n 為偶數 (即 n 可被 2 整除) ,則把 n 除以 2, 即 n => n/2;
若 n 為奇數 (即 n 不可被 2 整除) ,則把 n 乘 3 再加 1。 即 n => 3n+1。

若 n 為偶數 (即 n 可被 2 整除) ,則把 n 除以 2, 即 n => n/2;
若 n 為奇數 (即 n 不可被 2 整除) ,則把 n 乘 3 再加 1,以後再除以 2。 即 n => (3n+1) / 2。

於是在任何數的終結也會出現 1-4-2-1 或 1-2-1 的循環 (Cycle),但這亦無改其本性。

 

參考文獻及網址

Matthews, Keith "The Collatz Conjecture" from Some BCMath/PHP Number Theory Programs. http://www.numbertheory.org/php/collatz.html .

Tomas Oliveira e Silva "Computational verification of the 3x+1 conjecture. " http://www.ieeta.pt/~tos/3x+1.html.