發新話題
打印

[介紹] 3x+1 猜想 [未解決的數學題目]

推到噗浪
推到臉書

[介紹] 3x+1 猜想 [未解決的數學題目]

對於任何正整數 x ,如果它是偶數,就把它除以二,變成 x/2 ,如果它是奇數,就把它乘三倍再加1,變成 3x+1 (當然,這樣就變成偶數了)。對於任意整數 x ,一再重複上面的步驟,經過有限次步驟之後,是否最後都有可能變成 1 呢?

上面這就是 3x+1 猜想,或者也有別名 Collatz problem, Syracuse problem, Kakutani's problem, Hasse's algorithm, 還有 Ulam's problem 。

比如說從五開始的話, 5 → 5*3+1=16 → 16/2=8 → 8/2=4 → 4/2=2 → 2/2=1

當然可以把它畫的看一點,像是(下面的圖是 google 找來滴)

或是




關於這個問題,1996 年過世的大數學家 Paul Erdos(有書本翻作“艾狄胥”) (http://www.books.com.tw/exep/prod/booksfile.php?item=0010009939) 曾經思考過這個問題,然後下了一個評論 "Mathematics is not yet ready for such problems."



延伸閱讀:
網路上可以找到的
【中文的介紹】
1. http://hk.geocities.com/goodprimes/T3N.htm
【英文的介紹】
1. http://www.ericr.nl/wondrous/
2. 在 美國數學月刊 上的一篇介紹 http://www.cecm.sfu.ca/organics/papers/lagarias/
3. http://mathworld.wolfram.com/CollatzProblem.html
4. http://www.emathonline.com/interactive/3x+1.html
引用:
附上一篇大陸的介紹文章,
來自 http://www.oursci.org/magazine/200107/010714.htm

  3x+1問題    作者:異調

一、一個簡單的問題

當我們閱讀數學史時,會有這樣一種印象,數學家們首先研究簡單的
問題,然後研究越來越複雜的問題。經常性地,高深的數學問題是非
常複雜的。只是為了理解問題,我們就得學習非常多的數學知識;而
為了解決它,那就得用更複雜的數學知識了。就算我們在學校裡的數
學考試也是如此,最後一題經常被叫做「最後一大題」,「一大題」
是說它表達複雜,裡面還有一二三四的小題,要理解題意就得幾分鐘
的時間。弄不好還理解錯了,搞得整道題都白白做,被扣去許多分。

可是數學裡不只有這些嚇人的「大題」--我是說,數學裡還有嚇人
的「小題」。這樣的「小題」理解起來非常容易,卻讓無數數學家大
跌眼鏡,怎麼冥思苦想也不得其解。3x+1問題大概就是其中最著名而
又最簡單的一個。它簡單到大概任何一個會除2和會乘3的人(比如說,
沒文化但是經常買菜的老奶奶)都能理解它的意思,但是困難得讓數
學家至今也沒有找到好好對付它的方法。

任取一個自然數,如果它是偶數,我們就把它除以2,如果它是奇數,
我們就把它乘3再加上1。在這樣一個變換下,我們就得到了一個新的
自然數。如果反覆使用這個變換,我們就會得到一串自然數。

比如說我們先取5,首先我們得到3*5+1=16,然後是16/2=8,接下去
是4,2和1,由1我們又得到4,於是我們就陷在4→2→1這個循環中了。

再舉個例子,最開始的數取7,我們得到下面的序列:
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
這次複雜了一點,但是我們最終還是陷在4→2→1這個循環中。

隨便取一個其他的自然數,對它進行這一系列的變換,或遲或早,你
總會掉到4→2→1這個循環中,或者說,你總會得到1。已經有人對所
有小於100*250=112589990684262400的自然數進行驗算,無一例外。

那麼,是否對於所有的自然數都是如此呢?

這看起來是個多麼簡單的問題啊!


二、克格勃的陰謀?

這個問題大約是在二十世紀五十年代被提出來的。在西方它常被稱為
西拉古斯(Syracuse)猜想,因為據說這個問題首先是在美國的西拉古
斯大學被研究的;而在東方,這個問題由將它帶到日本的日本數學家
角谷靜夫的名字命名,被稱作角谷猜想。除此之外它還有著一大堆其
他各種各樣的名字,大概都和研究和傳播它的數學家或者地點有關的:
克拉茲(Collatz)問題,哈斯(Hasse)算法問題,烏拉姆(Ulam)問題等
等。今天在數學文獻裡,大家就簡單地把它稱作「3x+1問題」。

角谷靜夫在談到這個猜想的歷史時講:「一個月裡,耶魯大學的所有
人都著力於解決這個問題,毫無結果。同樣的事情好像也在芝加哥大
學發生了。有人猜想,這個問題是蘇聯克格勃的陰謀,目的是要阻礙
美國數學的發展。」不過我對克格勃有如此遠大的數學眼光表示懷疑。
這種形式如此簡單,解決起來卻又如此困難的問題,實在是可遇而不
可求。

數學家們已經發表了不少篇嚴肅的關於3x+1問題的數論論文,對這個
問題進行了各方面的探討,在後面我會對這些進展作一些介紹。可是
這個問題的本身始終沒有被解決,我們還是不知道,「到底是不是總
會得到1?」

在1996年B. Thwaites懸賞1100英鎊來解決這個問題。我寫一下這個
懸賞的文獻:Thwaites, B. 「Two Conjectures, or How to win
£1100.」Math.Gaz. 80, 35-36, 1996,好在大家萬一證出來時知
道跑哪裡去領獎。看在錢大爺的份上,3x+1問題於是又多了個名字,
叫Thwaites猜想。

要是真的有這麼一個自然數,對它反覆作上面所說的變換,而我們永
遠也得不到1,那只可能有兩種情況。

1)它掉到另一個有別於4→2→1的循環中去了。我們在後面可以看到,
要是真存在這種情況,這樣一個循環中的數字,和這個循環的長度,
都會是非常巨大的;
2)不存在循環。也就是說,每次變換的結果都和以前所得到的所有結
果不同。這樣我們得到的結果就會越來越大(當然其中也有可能有暫
時減小的現象,但是總趨勢是所得的結果趨向無窮大)。

因為這是個形式上很簡單的問題,要理解這個問題所需要的知識不超
過小學三年級的水平,所以每一個數學愛好者都可以來碰碰運氣,試
試是不是能證明它。不過在這裡我要提醒大家的是,已經有無數數學
家和數學愛好者嘗試過,其中不乏天才和世界上第一流的數學家,他
們都沒有成功。如果你在幾小時內就找到了一個「證明」,那麼把它
一步一步地嚴格地寫下來,看看是不是嚴密正確(我可以肯定它是錯
的,我這樣的肯定要冒的危險絕不超過連續中十次彩票頭獎的機率,
既然我不買彩票,我就沒道理不這麼肯定:-))。事實上,在互聯網上
已經有一些錯誤的「證明」。據說還有個數學愛好者跑到公證處去公
證他的「證明」,生怕別人把他的好主意偷跑了。

二十多年前,有人向偉大的數論學家保爾•艾狄胥(Paul Erdos)介
紹了這個問題,並且問他怎麼看待現代數學對這問題無能為力的現象,
厄爾多斯回答說:「數學還沒有準備好來回答這樣的問題。」


三、一些概念,一些紀錄

雖然證不出猜想,但是數學家們還是得到了許多很可能很有用的結論。
讓我們先來定義幾個概念,然後再來介紹這些結論。

從一個自然數開始,用上面這個變換,我們可以計算出一串自然數的
序列。為了形象起見,我們把這串數列叫做以最初用來開始計算的那
個自然數命名的「航班」。比如說,第6次航班就是
6→3→10→5→16→8→4→2→1
我們把一個航班裡的最大數字,叫做這個航班的「最大飛行高度」。
比如說,第6次航班的最大飛行高度就是16。我們把航班在數字1「著
陸」之前的數字個數(最初的數字包含在內,但1不包含在內),叫
做這個航班的「航程」(特別定義第1次航班的航程為0)。第6次航
班的航程就是8。如果真有自然數在此變換下永遠達不到1,那麼這個
航班的航程就是無窮了。

接下去的概念稍微有點複雜。我們把從起點開始(但不包括起點)連
續的不小於起點的數字的個數,叫作「保持高度航程」。舉一個例子
來說明這個概念比較方便:第11次航班是
11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
我們看到從起點開始,34,17,52,26,13,40,20都不小於起點11,
共有7個數字,所以第11次航班的保持高度航程為7。後面的航程中雖
然還有數字16大於起始點11,但是它不被算在保持高度航程裡了。一
個最簡單的推論就是,偶數次航班的保持高度航程總是0,因為開始就
除以2,跌到較低的高度去了。

為什麼我們對一個航班的保持高度航程感興趣?因為如果所有航班的
保持高度航程都是有限的話,3x+1問題就成立了。讓我們假設已知所
有航班的保持高度航程都是有限的,用數學歸納法來證明3x+1問題,
也就是所有的航班都在1上「著陸」。我們已經知道第1到第5航班都
是在1上著陸的,現在假設對於所有小於n的數字k,第k次航班都在1
上著陸,我們來看看第n次航班的情況:由於按假設它的保持高度航
程是有限的,所以它遲早會降落在一個比n小的數字上--於是按歸
納假設它就會降落在1上!

我們可以對開始的30班航班列出一個相關數據表來:

航班 航程 保持高度航程 最大飛行高度
1 0 0 1
2 1 0 2
3 7 5 16
4 2 0 4
5 5 2 16
6 8 0 16
7 16 10 52
8 3 0 8
9 19 2 52
10 6 0 16
11 14 7 52
12 9 0 16
13 9 2 40
14 17 0 52
15 17 10 160
16 4 0 16
17 12 2 52
18 20 0 52
19 20 5 88
20 7 0 20
21 7 2 64
22 15 0 52
23 15 7 160
24 10 0 24
25 23 2 88
26 10 0 40
27 111 95 9232
28 18 0 52
29 18 2 88
30 18 0 160

下面要說說幾個記錄。在上面我們已經說過,目前3x+1問題已經被檢
驗到100*250=112589990684262400,都沒有發現反例。這是葡萄牙阿
弗羅(Aveiro)大學的Tomas Oliveira e Silva的工作,用了很巧妙
的編程方法。他的主頁在 http://www.ieeta.pt/~tos/3x+1.html

如果一個航班的航程大於所有它前面的航班的航程,我們就把它叫作
「航程紀錄航班」,比方說第7航班,它的航程是16,比第1到6次航班
的航程都長,所以第7航班是個航程紀錄航班。今天我們已經知道的航
程紀錄航班有118個,航程最長的是2234047405400065次航班,它的
航程是1871,這是Eric Roosendaal發現的,他有個個人網站
http://personal.computrain.nl/eric/wondrous/
裡面有各種各樣關於3x+1問題的信息,下面的記錄也都來自這個網站。

同樣的,如果一個航班的保持高度航程大於所有它前面的航班的保持
高度航程,我們就把它叫作「保持高度航程紀錄航班」,比方說從上
面的表中我們看到第7航班也是個保持高度航程紀錄航班。今天已知的
保持高度航程紀錄航班有30個,航程最長是1008932249296231次航班,
它的保持高度航程是1445。

最大飛行高度記錄航班就是那些最大飛行高度記錄大於所有它前面的
航班的那些航班,現在已知的有76個,最大的是10709980568908647
次航班,到達了350589187937078188831873920282244的高度。

對於一個固定航班N,考慮它在1著陸之前所作的變換,如果把其中除
以2的變換稱為「偶變換」並記為E(N),而把乘以3再加1的變換稱為
「奇變換」並記為O(N)。數學家已經證明,O(N)/E(N)<log2/log3。
我們注意到,對有些航班來說,O(N)/E(N)非常接近於log2/log3?
0.63092975……。有猜想認為它會越來越接近這個數字(也有相反的
猜想,認為不會無限接近),所以大家為此設立了另一個紀錄,就是
這個比值比所有以前的航班更接近log2/log3的航班。這樣的紀錄不多,
現在已知的有15個,其中最後一個是N=100759293214567,I(N)/P(N)
?0.604938。值得一提的是N=104899295810901231,它的這個比值
還要更靠近,達到0.605413,但是我們不知道它是否是一個紀錄,也
就是說,我們不知道所有比它小的航班裡,是否還有比這個比值更靠
近log2/log3的。

我們知道,對於任何p,總有至少一個航班,它的航程是p:
2p→2p-1→2p-2→……→4→2→1
但是一般並不需要這麼大的航班,就可以達到航程p。在2000年有人提
出要找到最小的航班號,使得它的航程恰好是2000。現在最好的紀錄
是第67457283406188652次航班,但誰都不知道這是不是最小的航程為
2000的航班。

計算一個航班的算法是非常簡單的--只要除2或乘3加1。但是為了檢
驗大量的和航次巨大的航班,巧妙的編程方法是非常重要的。上面的
那些紀錄都是由幾台類似於我們平時使用的那樣的計算機得到的結果。
但是如果沒有好好地思考和編程,光是硬算,那麼使用最先進的計算
機恐怕也得不到這樣的結果。

為了驗證一個航班的確在1上著陸,並不一定需要把結果計算到1。如
果你已經驗證了所有航次小於n的航班都在1上著陸,那麼對於第n次航
班,你只要把結果計算到一個小於n的數m就可以了--我們已經驗證
過第m次航班在1上著陸。事實上,如果我們只要計算到一個以前的航
班飛行時到達過的數值就可以了,當然這需要記住以前已經到達過的
比較高的高度,這裡也必須巧妙地編程使得這樣的記憶所使用的內存
比較少。

更重要的是使用數學方法去減少計算量。比如說,任何n=4k+1的航班
最終都會飛到一個比n更小的高度。首先這是奇數,我們乘3加1得到
12k+4,然後連除兩次2,就有3k+1<n。所以我們沒有必要費功夫去驗
證4k+1型的航班。另外偶數次航班第一次變換就被除以2,降低了高
度,所以同樣也不需專門驗證。只用這樣一個小技巧,我們就使計算
量減少到原來的25%。

如果按照這樣的思路下去,我們同樣不需要考慮16k+3型的航班,只
要考慮到前面的飛行記錄:
16k+3→48k+10→24k+5→72k+16→36k+8→18k+4→9k+2→……
而9k+2<16k+3。

我們可以這樣追蹤下去,考慮256k+i型的航班,其中i取0到255,那
麼我們會發現我們需要考慮的類型只有i=27、31、47、63、71、91、
103、111、127、155、159、167、191、207、223、231、239、251、
255。這樣我們要作的計算只有最初的8%不到。

而Eric Roosendaal得到上面那些紀錄的程序,是建立在對65536k+i
型航班分析的基礎上的,其中只有1729種航班需要真正的檢驗(只有
原來計算量的2.6%)。他的程序還使用了其它的算術技巧,以及可以
同時計算好幾個航班。Tomas Oliveira e Silva進一步改進了這些技
巧,從而使得他成為現在3x+1問題驗證的世界紀錄保持者(他的計算
從1996年8月開始,到2000年4月結束,其間使用了兩台133MHz和兩台
266MHz的DEC Alpha計算機)。Eric Roosendaal還在和其他人一起
合作進行計算(包括再次驗證以前的結果),如果你願意加入這個研
究項目的話,可以去訪問上面給出的他的主頁。


四、理論結果

只要稍微動一下腦筋,我們就知道3x+1問題和下面幾個命題都是等價
的:
1)所有的航班的航程都有限;
2)所有的航班的保持高度航程都有限;
3)所有的航班中的偶變換的次數都有限;
4)所有的航班中的奇變換的次數都有限;
5)所有的航班的保持高度航程中偶變換的次數都有限;
5)所有的航班的保持高度航程中奇變換的次數都有限。

R. Terra和C. Everett證明了,「幾乎所有(almost everywhere)的航班都會下降到它的起
始點以下」,也就是說「幾乎所有的航班的保持高度航程都有限」。
這裡的「幾乎所有(almost everywhere)」是有確定的數學意義的,它是指:

--存在一個自然數n1,在所有小於n1的航班裡,最多只可能有1/10
的航班,它們的保持高度航程無限;
--存在一個自然數n2,它比上面的n1要大,在所有小於n2的航班裡,
最多只可能有1/100的航班,它們的保持高度航程無限;
--存在一個自然數n3,它比上面的n2要大,在所有小於n3的航班裡,
最多只可能有1/1000的航班,它們的保持高度航程無限;
--等等等等……

這好像很接近證明「所有的航班的保持高度航程都有限」了,於是很
接近證明猜想本身了。但是好好想想,這個結論只不過是說明保持高
度航程無限的航班會越來越稀少罷了,它們還是有可能存在的……更
糟糕的是,這個結論一點也沒有排除有其它循環存在的可能。

對於在1上著陸的航班,數學家們也得到了一些結果。他們證明了,存
在一個常數c,當n足夠大的時候,在比n小的航班中,能夠在1上著陸
的航班的個數大於等於nc。在1978年R. Crandal首先給出c=0.05,雖
然小了點,但畢竟是開頭一步;然後J. Sander給出c=0.3;在1989年
I. Krasikov得到c=0.43;1993年G. Wirsching得到c=0.48;最後在
1995年D. Applegate和J. Lagarias得到c=0.81。看起來我們越來越
接近c=1這個最終目標了。可是我們不知道現在用來得到c的方法是否
還可以再用下去,就好像在試圖征服哥德巴赫猜想的過程中,陳景潤
用來證明1+2的方法,似乎不能用來證明1+1了。

1995年的這個證明相當特殊。它使用了計算機程序來解一個十分巨大
的方程組,所以這個證明不能用手工來驗證。在論文中,我們看見的
不是一個關於c=0.81的定理的證明,而是一個關於如何寫出這個巨大
方程組的說明,和由程序計算出來的結果,以及如何使用這些結果來
解釋c=0.81。其他的數學家如果想驗證這個結果,必須首先看懂關於
方程組的證明和那些解釋,再按照裡面的說明來寫一個程序(很複雜
的!),運行它,再看看結果是否和文章中的相同。目前四色定理的
證明也是如此,所以數學家對此很不滿意。

還有一些結果是關於如果有其他不同於4→2→1的循環存在時,對這樣
的循環的性質的研究。R. Crandal和N. Yoneda在1978年證明,如果
這樣一個另外的循環存在的話,那麼它的長度(就是在這個循環中數字
的個數,比如說循環4→2→1的長度就是3)一定要大於275000。1993
年這個體積增大到17087915,最近的結果是102225496。這些結果是
通過分析包括我們前面提到的各種紀錄得到的,所以這些結果我們還
是不能完全通過手工來驗證。我們看到,如果真有另外的循環存在的
話,那一定是非常非常巨大的!


五、啟發式論證

數學中有一種叫「啟發式」的論證方法,建立在統計和機率的手段上。
比如說底下的論證方法就是這個類型的:

「每個數字要麼是奇數要麼是偶數,如果隨便取一個自然數,碰到奇
數和偶數的可能性是一樣的。如果我們把一次航班中這一系列數值看
作是隨機的話,那麼使用奇變換和偶變換的可能性也是一樣的,所以
平均在每兩次變換中我們有一次是n→3n+1,有一次是n→n/2。所以平
均起來,每次飛行高度的變化就是乘以3/2,於是……就會越飛越高。」

這樣的啟發式論證就推翻了原來的猜想!但是這個論證顯然比較幼稚,
因為它沒有考慮到,每一次奇變換後隨即而來的一定是一次偶變換,
因為如果n是奇數的話,3n+1一定是偶數;而每一次偶變換後隨即而
來的卻不一定是一次奇變換。J. Lagarias改進了這個啟發式論證。
他指出,如果我們把奇變換後再作偶變換考慮在一起,那麼這樣得到
的結果可以看作是真的「很隨機」。於是有1/2的可能性它是奇數,
有1/4的可能性是一個奇數的2倍,有1/8的可能性是一個奇數的4倍,
等等。於是飛行高度的變化就是以下變換的「平均效應」;

--n乘以3/2,這有1/2的可能(奇變換後再作偶變換的結果為奇數);
--n乘以3/4,這有1/4的可能(奇變換後再作兩次偶變換);
--n乘以3/8,這有1/8的可能(奇變換後再作三次偶變換);
…………

於是平均來講,每次變換後高度的變化就是
c=(3/2)1/2(3/4)1/4(3/8)1/8(3/16)1/16……=3/4
所以高度在總體上來說應該是越來越低,每次大約低25%,最終降到
一個循環上(不過這個論證沒有排除有除了4→2→1以外的其他循環)。
這個論證可以使我們使用論證中的模型來計算出,從一個自然數開始,
平均要多少步的這樣的飛行(就是保持高度航程中奇變換的次數),
可以使飛行高度降到起始點以下。理論上的數值是3.49265……。如
果我們對3到2000000000(二十億)之間的航班的保持高度航程中奇
變換的次數取平均值,我們得到3.4926……。這兩個結果驚人的一致
性使我們相信上面的啟發性模型是正確的。如果它是正確的,那麼就
意味著沒有保持高度航程無限的航班,於是3x+1猜想就是正確的,至
少可以得出沒有飛得越來越高的航班的結論。

可是一個啟發性論證,就算再有實驗證據來表明它是對的,也只不過
是個論證,只能使我們對猜想的正確性更充滿信心。它不能代替真正
的數學證明。比如說,數學家猜想在π的十進位小數表示當中,出現
0到9各個數字的可能性是一樣的,對π的數值計算也強烈支持這個猜
想,可是如果沒有數學證明,它還是得被叫做一個猜想,而不是定理。

用上面這個啟發式的機率模型,我們還可以預言,對於第n次航班,它
的最大飛行高度不會超過Kn2(對於某個常數K)。數值計算表明對於
K=8,這個公式是正確的(同樣地,這可以讓我們提出猜想,而不是證
明定理)。


六、會不會永遠證不出來?

自從哥德爾發表了他的著名的不完備性定理以來,每次碰到一個十分
困難的問題時,數學家們就免不了疑神疑鬼--這會不會證不出來?

哥德爾的不完備性定理說,在包含皮亞諾的自然數公理的數學公理系
統中,總有不可證明的命題存在。公理系統的這種性質叫不完備性。
比如說,如果我們只取歐氏幾何的前四條公理,那麼平行公理是不能
用這前四條公理證明出來的,也就是說只有前四條公理的平面幾何是
不完備的(這個例子不是很嚴格,因為歐幾里德的公理系統在現代觀
點下是不嚴密的,但是我舉這個例子只是為了說明不完備性這個概念,
所以關係不大)。

所以說,如果我們只用皮亞諾的自然數公理,甚至再加上現代的集合
論公理系統,也有可能不能證明3x+1問題。甚至即使3x+1猜想其實是
錯誤的,我們也有可能不能證明這一點。比如說,我們可能發現一個
航班,我們對它進行計算,發現它飛得越來越高,但是無論如何不能
證明它永遠也不會回到1上來。

當然無論什麼數論問題都有可能搞得數學家們這樣疑神疑鬼,雖然其
實是他們還沒有發現證明。不過有一些蛛絲馬跡表明我們有必要稍微
嚴肅點看待此問題,因為3x+1問題離不可證明的問題並不太遠。

J. Conway(喜歡數學遊戲的朋友可能會記起這個名字來,著名的生命
遊戲就是他發明的)在1972年考慮了3x+1問題的推廣形式。在3x+1問
題裡,我們把數字除以2,然後得到了2種可能的餘數(0或者1),按
照餘數我們使用2個公式(除以2或者乘3加1)。Conway考慮了除以一
個固定的p,按照餘數的不同(這時就有p種不同的餘數)分別使用p個
公式的情況。然後他提出了一個類似「在1著陸」的猜想。他在論文中
證明了,這個猜想在集合論公理系統中是不可證的。

事實上,在任何一個包含了皮亞諾的自然數公理的數學公理系統中,
Conway的方法都可以定義一個類似於3x+1問題的不可證命題。當然這
不是說有一個在所有公理系統中都不可證的命題。「不可證」總是相
對於某公理系統而言的。當然,Conway的方法並沒有說明3x+1問題本
身是不可證的,也沒有說它一定是很困難的(事實上有些3x+1問題的
變種是很容易解決的),但是這畢竟說明,有些很像3x+1問題的命題
是不可證的,這把事情搞得很可疑。

1993年,法國裡爾(Lille)的基礎信息實驗室使用了Conway的方法來
演示一套基於邏輯規則的編程形式的威力。同許多數學中的例子一樣,
先頭看上去最沒用的課題,會有很具體的用處。


七、各種變種

數學家總喜歡把問題推廣,使它更抽像化和一般化,因為這樣可以把
一種在具體某個問題上使用的方法的威力應用到一般的情況上去,從
而得到很有可能是出乎意料的結論。

數學家們首先考慮,如果把3x+1問題的規則運用到負整數上去,會產
生什麼現象。他們發現了三個不同的循環:
1)-1→-2
2)-5→-14→-7→-20→-10
3)-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122
→-61→-182→-91→-272→-136→-68→-34
他們猜想,這就是所有的循環,而所有的負整數都會掉進其中一個裡。

他們還提出了5x+1問題,也就是在奇數的情況下用5x+1來取代3x+1。
這下又有好幾個循環:
1)6→3→16→8→4→2→1
2)13→66→33→166→83→416→208→104→52→26
3)17→86→43→216→108→54→27→136→68→34
但是5x+1問題中的第7次航班好像老在那裡飛啊飛,怎麼也跑不到一個
循環裡去,但是誰都不能證明的確如此。

上面 Lagarias 的那個啟發式論證使得數學家猜想,如果q是大於3的奇
數的話,對於qx+1問題,總存在至少一個航程無窮的航班,這看起來
很像是一個「反3x+1問題」。

還有許多其他的3x+1問題的推廣,一些結果把它們和其它數學領域聯
繫起來,比如說素數理論,某些丟番圖方程(求解係數為整數的方程
的整數根,比如著名的費爾馬大定理就是一個丟番圖問題),馬爾可
夫鏈(機率論中的遞歸理論),遍歷理論(一種關於函數混合遞歸的
理論)。

就算3x+1問題終於被解決了,看看所有這些變種,也夠數學家們自娛
自樂上幾百年的了。

TOP

發新話題