主題
Search

196演算法


取任意兩位或更多位的正整數,反轉數字,然後加到原始數字上。這是反向相加序列的操作。現在,對獲得的重複此過程,直到獲得迴文數。此過程通常會快速產生迴文數,對於大多數整數。例如,從數字 5280 開始產生序列 5280, 6105, 11121, 23232。對 1, 2, 3, ... 應用該演算法的最終結果是 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 11, 33, 44, 55, 66, 77, 88, 99, 121, ... (OEIS A033865)。 89 的值特別大,為 8813200023188。

未知是否能產生迴文數的首批數字,有時被稱為 Lychrel 數 (VanLandingham),是 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, ... (OEIS A023108)。

透過迭代地將演算法應用於 196(最小的此類數字)獲得的數字是 196, 887, 1675, 7436, 13783, ... (OEIS A006960),並且這個序列中沒有已知的迴文數成員。因此,特殊數字 196 適合用作反向相加演算法的名稱。1990 年,John Walker 計算了 196 演算法的 2415836 次迭代,並獲得了一個具有 1000000 位數的數字。1995 年,Tim Irvin 將此擴充套件到獲得了一個具有 2000000 位數的數字。M. Sofroniou(私人通訊,2002 年 2 月 16 日)給出了一個高效的 Wolfram 語言 實現,其複雜度為 O(k^2),對於 k 步,在 450 MHz Pentium II 上大約需要 10.6 小時來計算 250000 次迭代。推斷時間資料表明,在同一臺機器上大約需要 42 天才能達到 Walker 的 2415836 次迭代。

關於rec.puzzles存檔錯誤地指出,在 9480000 次迭代後獲得了一個 3924257 位數的非迴文數。然而,正確的結果數字是 3924578 位數長。截至 2006 年 5 月 1 日,經過 724756966 次迭代後,已確定最終的迴文數將超過 3 億位數 (VanLandingham)。

n 生成迴文數所需的迭代序列中的項數 a(n) (即,對於迴文數 a(n)=1,如果在 196 演算法的一次迭代後產生迴文數,則 a(n)=2,等等)對於 n=1, 2, ... 是 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 1, ... (OEIS A030547)。達到迴文數所需的迭代次數 n=0, 1, 2, ... 的最小數字是 0, 10, 19, 59, 69, 166, 79, 188, ... (OEIS A023109)。


另請參閱

加法永續性, 數字加法, Lychrel 數, 乘法永續性, 迴文數, 迴文數猜想, RATS 序列, 迴圈數字不變數, 反向相加序列

使用 探索

參考文獻

De Geest, P. "關於使用反向求和使 '196' 變成迴文數的網路資源。" http://www.worldofnumbers.com/weblinks.htm.Eddins, S. "數字的迴文階。" IMSA Math. J. 4, Spring 1996. http://www.imsa.edu/edu/math/journal/volume4/webver/palinord.html.Gardner, M. 數學馬戲團:來自《科學美國人》的更多謎題、遊戲、悖論和其他數學娛樂。 New York: Knopf, pp. 242-245, 1979.Gruenberger, F. "如何處理數千位數的數字,以及為什麼要這樣做。" Sci. Amer. 250, 19-26, Apr. 1984.Irving, T. "關於兩個月的計算,或者,沃克先生三年計算的附錄" http://www.fourmilab.ch/documents/threeyears/two_months_more.html.Math Forum. "Dr. Math 問答:將數字變成迴文數。" http://mathforum.org/dr.math/problems/barnes10.11.html.MathPages. "導致迴文數的數字反向求和。" http://www.mathpages.com/home/kmath004.htm.Peters, I. J. "搜尋最大的數字迴文數。" http://www.floot.demon.co.uk/palindromes.html.rec.puzzles 存檔。 1996. ftp://rtfm.mit.edu/pub/usenet/news.answers/puzzles/archive/arithmetic/part1.Sloane, N. J. A. 《整數序列線上百科全書》中的序列 A006960/M5410, A023108, A023109, A030547, 和 A033865VanLandingham, W. "196 和其他 Lychrel 數。" http://www.p196.org/.Walker, J. "三年計算:關於迴文數探索的最終報告。" http://www.fourmilab.ch/documents/threeyears/threeyears.html.

請這樣引用

Weisstein, Eric W. "196-演算法。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/196-Algorithm.html

主題分類