主题
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 序列, 循环数字不变量, 反向相加序列

使用 Wolfram|Alpha 探索

参考文献

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-算法。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/196-Algorithm.html

主题分类