196迴文數探索

在自然數中，有一種從左往右，從右往左讀起來都相同的數，叫做“迴文數”，例如11,101,121,1111等。

如果有一個數不是迴文數，比如説19，那麼把它左右兩邊順序的數相加：19+91=110，繼續相加：110+011=121,得到121就是迴文數。

再比如253：

1111就是迴文數。 ^[1] 

我們不知道是否所有的自然數都有這樣的規律。

如果有一個數無法通過上面的步驟得到迴文數，這個數就叫利克瑞爾數，196就是最小的“疑似”利克瑞爾數，到底是不是，誰也不知道，就這麼一個看起來簡單相加的問題，2018年還沒人能證明，如果有人能用理論來證明是否存在利克瑞爾數，而不是暴力相加，沒準能從證明過程中發現新的大陸。 ^[1] 

1987年8月12日，約翰·沃克（John Walker）在Sun 3/260工作站（使用Motorola 68020微處理器）上啓動了一個程序，使搜索更進一步。1990年5月24日午夜前五分鐘，差不多三年後，他的程序在2415836次迭代後結束，產生了一個1000000位數的數字——看不到迴文數。第二天，沃克在互聯網上的一個網頁“三年計算”（Three Years Of Computing）上向人們提供了這個1000000位數的數字和他的程序，任何人都可以在不重複三年工作的情況下繼續他的探索。

自從1984年出版的《科學美國人》（Scientific American）雜誌以來，蒂姆·歐文（Tim Irvin）就對迴文搜索產生了興趣。1995年，他發現自己可以使用一台超級計算機，即併發計算機公司（Concurrent Computer Corporation）的Maxion 9502型。在互聯網上搜索已經完成的迴文搜索工作，他找到了約翰·沃克（John Walker）的網頁。他“借用”了他的程序，在程序員拉里·西姆金斯（Larry Simkins）的幫助下，他們再次啓動了這個程序，繼續從1000000位數字開始的探索。1995年8月22日，經過大約兩個月的計算，該程序在計算了196到2百萬位數字後停止運行。蒂姆的超級計算機在兩個月內就完成了三倍於約翰·沃克三年工作所需的計算量，其計算機世代相差8年。這個數字可以從Tim的網頁“大約兩個月的計算”中獲得，任何希望自己繼續探索的人都可以使用。

因為傑森·杜塞特（Jason Doucette）創建了一個彙編語言程序，它可以在普通台式計算機上執行必要的計算，比以前在超級計算機上使用的未優化程序更快。（請注意，為計算196迴文問句而創建的原始程序是為了節省內存，犧牲了速度。儘管存在這些顧慮，但杜塞特發現這些程序錯過了某些優化，這些優化可以在不犧牲速度的情況下節省相同數量的內存，以及某些對內存使用沒有任何影響的優化）。

杜塞特的程序於1999年8月9日星期一在奔騰II 266兆赫PC上開始計算196迴文數。

該計劃在1天18小時內達到了1000000位數的大關

杜塞特打算在某個時候重新測試，因為杜塞特的代碼被竊聽，導致它總共向屏幕和數據文件寫入了54兆字節的垃圾，從而減慢了計算速度。

該計劃在額外的5天10小時內達到了2000000位數的大關。

這兩個數字都與約翰·沃克和蒂姆·歐文的作品相符。杜塞特100%相信他的程序是無錯誤的，只要杜塞特有機會使用計算機的空閒時間，杜塞特就會繼續工作。

該計劃在額外的8天7小時內達到了300萬位數。

該計劃在額外的8天14小時內達到了4000000位數的大關。這是在1999年9月6日星期一實現的，打破了之前390萬位數的記錄（根據rec.puzzles檔案），比預期快了4天，這得益於賽揚400 MHz機器的幫助，該程序在該機器上運行了部分處理。

該計劃在13天8小時內達到了5百萬位數字。

該程序僅在賽揚400 MHz處理器上運行。

該計劃在另外14天4小時內達到了6百萬位數的大關。

該計劃在額外的26天12小時內達到了7百萬位數。

該計劃在33天23小時內達到了8百萬位數字。

該計劃在另外59天12小時內達到了9百萬位數的大關。

（這百萬位數的時間長度增加可能是由於該程序在此期間多次停止和繼續。）

該計劃在34天零1小時內達到了10百萬位數的大關。

該計劃在另外26天3小時內達到11百萬位數。

該計劃在另外28天零5小時內達到了12百萬位數。

該計劃在另外28天23小時內達到了13百萬位數。

（對於這一百萬個數字，該程序有奔騰III 450兆赫機器的一點幫助，儘管該程序在任何給定時間只能在一台機器上運行。）

該程序使用賽揚400兆赫機器平均每秒增加120萬個位數（即它可以在一秒鐘內增加兩個120萬位數）。這是每天增加1萬億個位數。

在杜塞特與伊恩·J·彼得（Ian J.Peter）通信後，他開始改進自己的迴文數程序。彼得正在計算所有整數，每個整數最高可達2000000000位。他在AMD Athlon 500兆赫系統上運行的手工優化組裝程序的速度是杜塞特在Intel Celeron 400兆赫上運行的程序的4到8倍。

速度快幾個因素：

他的程序已經在很大程度上進行了算法優化，以及裝配級的手工優化——但杜塞特不會在這裏透露任何秘密；這不是杜塞特要釋放的，所以請改問他。但杜塞特可以説一些技術註釋：

杜塞特的程序在386代碼中使用平面模式（非真實模式）32位尋址，使用Turbo Pascal 7.0，因為杜塞特缺少一個允許真正保護模式內存尋址的編譯器。這很有趣，因為Intel 80286（即286）處理器引入了這一功能（杜塞特的舊Tandy 1000 SX有一個）。Ian使用的是在Linux下運行的保護模式32位尋址，並利用了新機器上的新指令集。

就硬件而言，這是AMD第一次給杜塞特留下深刻印象。杜塞特有一台AMD K6-200MHz，杜塞特對此印象不深。杜塞特的3Dfx VooDoo2卡坐着等待處理器傳遞信息。但是，Athlon是另一個故事。它有256 KB的一級緩存（比Celerons的二級緩存多），是常規Pentium III系統的4倍。它有512 KB的二級緩存，但最多可以有8192 KB。這並不意味着你應該出去買一個。你應該購買對你的工作類型最有利的處理器。杜塞和彼得的迴文數程序的本質——考慮到代碼非常小，而且內存訪問總是按順序進行的——得益於Athlon架構，甚至比普通應用程序或遊戲更為明顯。

他的程序在短短5個多小時內達到了1000000個數字，在短短30天內達到了10000000個數字，運行在他專用的500MHz Athlon上。

伊斯特萬·博茲西克（István Bozsik）從其他人那裏找到了與杜塞特之前一樣的作品，如上所述。這激發了博茲西克的興趣，博茲西克很快發現自己也可以製作一個程序，以比他們更快的速度運行196迴文數。他於2000年5月7日編寫了自己的程序。

在他的網頁上，博茲西克顯示自己的搜索結果達到了600萬位數。不幸的是，杜塞特自己的工作已經超過了600萬位數。直到伊斯特萬取得成就之後，他才能夠通過搜索引擎找到杜塞特的網頁。他的網頁上有很多關於迴文數的鏈接。

杜塞特再也沒有時間繼續任務了。杜塞特把他的1350萬數字記錄交給了韋德·範蘭丁厄姆（Wade VanLandingham）。他接受了這個數字，並將其延續到超過3億位數（幾乎7.25億次迭代）。他在自己的網頁上，從各種來源收集了大量關於196迴文數的信息，196和其他利克瑞爾數值得一看。 ^[2] 

種子是利克瑞爾數的子集。

除了196之外，其它的利克瑞爾種子數也被暴力測試。

參考資料： ^[4]