利克瑞爾數

維基百科,自由的百科全書
前往: 導覽搜尋
未解決的數學問題196是利克瑞爾數嗎? Question mark2.svg

利克瑞爾數(Lychrel Number)指的是將該數與將該數各數位逆序翻轉後形成的新數相加、並將此過程反覆疊代後,結果永遠無法是一個迴文數自然數。「利克瑞爾」的名字是Wade VanLandingham杜撰出的,這是從他的女友Cheryl的名字經過簡單的字母換位而來。 在1至1000000的數字裡,發現有122962個不能產生迴文數字的可能性。

逆序相加的過程[編輯]

逆序並相加的過程是將一個數的各位逆序排列後再與原數相加,而得到兩者之和。例如: 56 + 65 = 121, 125 + 521 = 646, 9999 + 9999 = 19998

在將這種逆序相加的過程重複幾次後,對有些數來說可以很快地得到一個迴文數的結果,這樣的數就不是利克瑞爾數。 經過這樣的重複,所有一位數和兩位數最終都得到了迴文數的結果。10,000以下的數中,大約80%的數會在四步以內的疊代後形成迴文數;共大約90%會在七步以內形成迴文數。這裡有一些非利克瑞爾數的例子:

  • 56在一次疊代後形成迴文數:56+65 = 121.
  • 57在兩次疊代後形成迴文數:57+75 = 132, 132+231 = 363.
  • 59也不是利克瑞爾數,因為在三次疊代後也得到了一個迴文數結果:59+95 = 154, 154+451 = 605, 605+506 = 1111
  • 89經過少有的24次疊代(它是10,000以下的數中疊代次數最多的)而得到迴文數8813200023188.
  • 10,911最後得到迴文數4668731596684224866951378664,經過55次疊代.
  • 1,186,060,307,891,929,990花費了261次疊代而形成一個119位數的迴文數
    44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544
    該數是Most Delayed Palindromic Number中記載的目前已知的疊代次數最多的世界紀錄,它是由Jason Doucette的算法及程序(程序使用的是Benjamin Despres的逆序相加代碼)於2005年11月30日發現的。

0開始能找到的第一個看起來(但尚未證實)不能形成迴文數的數是一個三位數196,它(被認為)是最小的利克瑞爾數。

尚未證實[編輯]

在其他基數下,某些數可被證明經重複的逆序相加疊代後肯定不能形成迴文數,例如二進位中的10110。[1] 但對於196和其他的十進位數目前無法證明這點。

由於目前還不可能證明一個數永遠不能形成迴文數,所以「196和其他那些(看起來)不能形成迴文數的數是利克瑞爾數」這一命題僅是猜想而非已獲證明。能證明的僅是那些反例,即如果一個數最終能形成迴文數則它不是個利克瑞爾數。

因此196是第一個可能的利克瑞爾數。(OEIS中的數列A023108)中列出的最前面的可能的利克瑞爾數是:

196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997.

上面用粗體印出的數是利克瑞爾種子數(見下)。由Jason DoucetteIan PetersBenjamin Despres製作的電腦程式已經發現了其他(可能的)利克瑞爾數。實際上,Benjamin Despres的程序能辨別出目前已測試出的從1位數到16位數之間每種數位長度的利克瑞爾種子數。[2] Wade VanLandingham的站點列出了發現的不同位數的利克瑞爾種子數的總數。[3]

已將John Walker最初實施的暴力測試法改良以更好地利用疊代的優點。例如,Vaughn Suite設計了一個程序僅保存每次疊代結果的開頭和末尾的一些數位,這樣就能在進行上百萬次疊代時不必每次將整個疊代結果保存到文件中(如果不是迴文數,通常只對比開頭和末尾的若干位就能確定。在疊代結果是很大的數時,如果數字太多必須要使用磁碟文件進行輔助存儲則會嚴重影響疊代速度,這樣做則可避免這種影響,僅在保存的那些位完全相符時才須作進一步測試)[4] 。但是迄今為止,對逆序相加疊代過程還沒有設計出更好的算法

族線、種子和同族數[編輯]

Jason Doucette杜撰的術語族線(thread)指的是在逆序相加疊代中產生的那些可能或不能形成迴文數的那些數組成的序列。對任意給定的種子(seed),它都可和它的同族數(kin numbers)匯聚到相同的族線上。族線不包括最初的種子同族數,只包括它們匯聚後的序列中共有的那些數。

種子是利克瑞爾數的一個子集,它是這個非迴文數的產生族線中最小的那個數。種子本身可能是個迴文數。上面的列表中用粗體顯示了前三個例子。

同族數也是利克瑞爾數的子集,它包含了族線中除種子及任何能經一次疊代後匯聚於給定族線的數之外的所有其他數。該術語是由Koji Yamashita在1997年引入的。

196迴文數探索[編輯]

由於196十進位)可能是最小的利克瑞爾數,因而它受到了最多的關注。

1987年8月12日,John Walker在一台Sun 3/260工作站上開設了「196迴文數探索」網站。他設計了一個C語言程序來進行逆序相加疊代、並在每步疊代後檢查結果是否是個迴文數。該程序以低優先級運行於後台,它每隔兩小時以及在系統關機前生成一個檢查點文件,其中記錄了疊代進行的次數以及已達到的最新結果。在重新開機時它能自動從最後保存的檢查點文件中恢復狀態,繼續之前的計算。該程序運行了將近三年,於1990年5月24日按設計的指令終止,並顯示出信息:

Stop point reached on pass 2,415,836.
Number contains 1,000,000 digits.
(在2,415,836次疊代過程後到達終點。計算結果含有1,000,000個數字。)

從196開始經2,415,836次疊代過程後,形成了一個有一百萬個數字的數,然而這些疊代的結果之中沒有出現一個迴文數。Walker把他的發現連同最後的檢查點文件一起發布在網際網路上,並邀請其他人一起用得到的這個大數繼續尋找迴文數。

1995年,Tim Irvin擔起了這個挑戰,並在三個月裡用一台超級計算機計算到了兩百萬位以上,其間也未出現迴文數的結果。Jason Doucette繼而加入,並在2000年5月計算到了12,500,000個數位。Wade VanLandingham使用Jason Doucette的程序計算到1,300萬位,這成為加拿大少兒科學雜誌上發表的一項紀錄。從2000年6月起,Wade VanLandingham成為領軍人,他使用多位發燒友編寫的不同程序,到2005年7月26日,VanLandingham已經計算到了2億6千3百萬位以上(以每5到7天一百萬位的速度)。這之間的結果中仍未出現迴文數。

其他基於使用同樣的重複逆序相加的暴力測試法而可能是利克瑞爾數的數還有879, 1997, 7059和9999,對它們已進行了數百萬次疊代而未在結果中發現迴文數. [5]

特定進制中可能的最小利克瑞爾數[編輯]

(可能的)利克瑞爾數在不同的進制中也存在,以下列出一些進制中可能是利克瑞爾數的最小數字 (OEIS中的數列A060382):

進制 可能的最小利克瑞爾數 10進制表示
2 10110 22
3 10201 100
4 3333 255
5 10313 708
6 4555 1079
7 10513 2656
8 1775 1021
9 728 593
10 196 196
11 83A 1011
12 179 237
13 CCC 2196
14 1BB 361
15 1EC 447
16 19D 413
17 B6G 3297
18 1AF 519
19 HI 341
20 IJ 379
21 1CI 711
22 KL 461
23 LM 505
24 MN 551
25 1FM 1022
26 OP 649
27 PQ 701
28 QR 755
29 RS 811
30 ST 869


外部連結[編輯]