利克瑞爾數
 |
 | 此條目可參照英語維基百科相應條目來擴充。 |
利克瑞爾數（Lychrel Number）是將一個數字反轉並將所得數字相加，進行無數次反覆迭代後，始終無法形成迴文數的自然數。(例如：295+592=887，887+788=...)
「利克瑞爾（Lychrel）」的命名來自Wade VanLandingham對女友Cheryl的名字進行的字母換位。[1]
在數字1至1,000,000中，已知有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，它（被認為）是最小的利克瑞爾數。
族線、種子和同族數
[編輯]Jason Doucette杜撰的術語族線（thread）指的是在逆序相加迭代中產生的那些可能或不能形成迴文數的那些數組成的序列。對任意給定的種子（seed），它都可和它的同族數（kin numbers）匯聚到相同的族線上。族線不包括最初的種子或同族數，只包括它們匯聚後的序列中共有的那些數。
種子是利克瑞爾數的一個子集，它是這個非迴文數的產生族線中最小的那個數。種子本身可能是個迴文數。上面的列表中用粗體顯示了前三個例子。
同族數也是利克瑞爾數的子集，它包含了族線中除種子及任何能經一次迭代後匯聚於給定族線的數之外的所有其他數。該術語是由Koji Yamashita在1997年引入的。
尚未證實的結論
[編輯]在其他基數下，某些數可被證明經重複的逆序相加迭代後無法形成迴文數，例如二進制中的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 Doucette、Ian Peters和Benjamin Despres製作的計算機程序已經發現了其他（可能的）利克瑞爾數。實際上，Benjamin Despres的程序能辨別出目前已測試出的從1位數到16位數之間每種數位長度的利克瑞爾種子數。[2] Wade VanLandingham的站點列出了發現的不同位數的利克瑞爾種子數的總數。[3]
對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把他的發現連同最後的檢查點文件一起發布在互聯網上，並邀請其他人一起用得到的這個大數繼續尋找迴文數。
John Walker最初實施的暴力測試法經過了改良以更好地利用迭代的優點。例如，Vaughn Suite設計了一個程序僅保存每次迭代結果的開頭和末尾的一些數位，這樣就能在進行上百萬次迭代時不必每次將整個迭代結果保存到文件中（如果不是迴文數，通常只對比開頭和末尾的若干位就能確定。在迭代結果是很大的數時，如果數字太多則必須要使用磁盤文件進行輔助存儲就會嚴重影響迭代速度，這樣做則可避免這種影響，僅在保存的那些位完全相符時才須作進一步測試）[4] 。
1995年，Tim Irvin和Larry Simkins擔起了這個挑戰，在三個月裡用一台超級計算機計算到了兩百萬位以上，其間也未出現迴文數的結果。Jason Doucette繼而加入，並在2000年5月計算到了1250萬位。韋德·范·藍丁漢使用Jason Doucette的程序計算到1,300萬位，這成為加拿大少兒科學雜誌上發表的一項紀錄。從2000年6月起，藍丁漢成為領軍人。通過使用多位發燒友編寫的不同程序，藍丁漢達到了每5到7天一百萬次的迭代速度。到2005年7月26日，藍丁漢已經計算到2億6千3百萬位以上。2011年Romain Dolbeau使用分布式計算完成了十億次迭代，生成了413,930,770位的數字。2015年2月，他的計算結果達到了十億位數，但這之間的結果中仍未出現迴文數。所以誕生了兩個猜想，分別是必然迴文數猜想：任何整數經過重複倒置相加運算都能產生一個迴文數，和196無限變化猜想：對數字196進行倒置相加運算永遠不會產生迴文數。
迄今為止，對逆序相加迭代過程還沒有設計出較好的算法。
其他基於使用同樣的重複逆序相加的測試法而可能是利克瑞爾數的數還有879, 1997和7059，對它們已進行了數百萬次迭代而未在結果中發現迴文數. [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 |
外部連結
[編輯]- 196及其他利克瑞爾數（頁面存檔備份，存於網際網路檔案館）by Wade VanLandingham
- Benjamin Despres（頁面存檔備份，存於網際網路檔案館）
- Jason Doucette - 世界紀錄（頁面存檔備份，存於網際網路檔案館） - 196迴文數探索，最終產生迴文數中迭代次數最多的
- John Walker（頁面存檔備份，存於網際網路檔案館） - 歷時三年的計算
- Tim Irvin（頁面存檔備份，存於網際網路檔案館） - 關於歷時兩個月的計算