利克瑞尔数

**利克瑞爾數**（Lychrel Number）是將一個數字和該數字的各數位逆序排列後形成的新數相加，並將此過程反覆迭代後，最終形成的一個非迴文數的自然數。其名稱「利克瑞爾（Lychrel）」由 Wade VanLandingham 將他的女友 Cheryl 的名字經字母換位所得出。

在 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 萬位。Wade VanLandingham 使用 Jason Doucette 的程序計算到 1,300 萬位，這成為加拿大少兒科學雜誌上發表的一項紀錄。從 2000 年 6 月起，Wade VanLandingham 成為領軍人。通過使用多位發燒友編寫的不同程序，VanLandingham 達到了每 5 到 7 天一百萬次的迭代速度。到 2005 年 7 月 26 日，VanLandingham 已經計算到 2 億 6 千 3 百萬位以上。2011 年 Romain Dolbeau 使用分布式計算完成了十億次迭代，生成了 413,930,770 位的數字。2015 年 2 月，他的計算結果達到了十億位數，但這之間的結果中仍未出現迴文數。

迄今為止，對逆序相加迭代過程還沒有設計出較好的算法。

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

## 特定進制中可能的最小利克瑞爾數

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

## 外部連結

* 196 及其他利克瑞爾數（頁面存檔備份，存於網際網路檔案館）by Wade VanLandingham
* Benjamin Despres（頁面存檔備份，存於網際網路檔案館）
* Jason Doucette - 世界紀錄（頁面存檔備份，存於網際網路檔案館） - 196 迴文數探索，最終產生迴文數中迭代次數最多的
* John Walker（頁面存檔備份，存於網際網路檔案館） - 歷時三年的計算
* Tim Irvin（頁面存檔備份，存於網際網路檔案館） - 關於歷時兩個月的計算

## 參考文獻