196

196

這篇文章是在寫temporal那篇文章時,找資料發現的有趣東西,在那篇文章當中,我有說到目前 date 物件的各種問題,其中第六點是「不支援 Gregorian Calendar(格里曆)以外的日曆(例如農曆)」 ,然後我就好奇起來了,現在還有什麼其他的曆法在用呢?結果找著找著,就看到有個網站提供了很多曆法了線上轉換,像是 Julian Calendar(儒略曆)、Hebrew Calendar(希伯來曆)、Islamic Calendar(伊斯蘭曆)、Persian Calendar(波斯曆)等,用 JavaScript 寫的,而且在程式碼裡面宣告貢獻到 public domain。

由於整個網站非常老派,我就對作者起了興趣,發現這個網站 fourmilab.ch 的所有者是John Walker,Autodesk 的 founder 之一,他現在已經退休搬到瑞士去了,然後 fourmilab.ch 上就放了他的各種記錄,像是文章,其實就是 blog,看他結構感覺也是個 MovableType 站,還有閱讀清單,旅遊照片,例如他去過南極一趟,還有些他寫的書,例如Hacker's DietThe Autodesk File等。

然後,我在 fourmilab.ch 上看到了「Three Years Of Computing」這篇文章,標題就吸引了我進去仔細閱讀,這篇文章是在說迴文數(palindrome)挑戰,什麼是迴文數呢,「95277259」就是迴文數,不論是從頭開始還是反過來從尾開始都是相同的數字,那什麼是迴文數問題呢?首先你要拿到一個非迴文數的十進位數字,例如 362 好了,把他和自己的反轉相加:

>
   362
+  263
------
   625

結果不是迴文數,那繼續一樣的反轉相加運算:

>
   625
+  526
------
  1151
+ 1511
------
  1661

最後得到了一個迴文數 1661,迴文數問題就是,是否所有的正整數都可以透過這樣的運算,不管幾次,最終可以得到迴文數,如果有數字無法透過這個過程變成迴文數,那這數字也可以稱為Lychrel Number,不過因為目前無法從理論證明一個十進位數是 Lychrel Number,就只能想辦法反證它(註:我有看到說二進位數有證明)。

文裡說到,所有小於一萬的數字都已經被測試過,大部分的數字都可以用很少的次數就得到迴文數,其中,最小的可能的 Lychrel Number: 196 ,到目前還無法讓它經由反轉相加的過程變為迴文數,John Walker 那個跑了三年的程式就是在驗證 196 到底能不能透過反轉相加的過程。他在 1987 年用他的 Sun 工作站開始跑,結果跑了三年後的 1990,達到他當初設的停止條件,100 萬位,總共反轉相加了 2415836 次,他還放上他的程式碼還有計算的結果,如果有人有興趣可以從這邊開始接手繼續算下去,事實上,當初他跑這程式的工作站性能和現在的電腦比起來差距實在很大,在其它人後來的挑戰當中,就有提到一些性能數字,例如 Ian J. Peter 的程式只需要 5 小時就可以計算到一百萬位,用的電腦大約是 500 MHz 的 CPU。

John Walker 在 1990 年跑到一百萬位,結果還沒得到迴文數,那麼現在最新的紀錄是多少呢?p196.org這網站收集了很多相關的資訊,對這議題有興趣的人還可以去看看,而它站上的紀錄是 413,930,770,四億多位,總共反轉相加了十億次;至於我目前看到的最高紀錄,是在「The p196_mpi page」這裡,提供了平行版的程式,而據作者 Romain Dolbeau 所說,他在 2015 年 2 月已經計算到十億位了,不過他沒提供相關資料,有提供的只有 2012 年的六億位結果。

comments powered by Disqus