利克瑞尔数
维基百科，自由的百科全书
利克瑞尔数（Lychrel Number）指的是将该数与将该数各数位逆序翻转后形成的新数相加、并将此过程反复迭代后，结果永遠無法是一个回文数的自然数。“利克瑞尔”的名字是Wade VanLandingham杜撰出的，这是从他的女友 Cheryl 的名字经过简单的字母换位而来。
目录 |
[编辑] 逆序相加的过程
逆序并相加的过程是将一个数的各位逆序排列后再与原数相加，而得到两者之和。例如： 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，它（被认为）是最小的利克瑞尔数。
[编辑] 尚未证实
在其它基数下，某些数可被证明经重复的逆序相加迭代后肯定不能形成回文数，[1] [2] 但对于 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 位数之间每种数位长度的利克瑞尔种子数。[3] Wade VanLandingham 的站点列出了发现的不同位数的利克瑞尔种子数的总数。[4]
已将 John Walker 最初实施的暴力测试法改良以更好地利用迭代的优点。例如，Vaughn Suite设计了一个程序仅保存每次迭代结果的开头和末尾的一些数位，这样就能在进行上百万次迭代时不必每次将整个迭代结果保存到文件中（如果不是回文数，通常只对比开头和末尾的若干位就能确定。在迭代结果是很大的数时，如果数字太多必须要使用磁盘文件进行辅助存储则会严重影响迭代速度，这样做则可避免这种影响，仅在保存的那些位完全相符时才须作进一步测试）[5]。但是迄今为止，对逆序相加迭代过程还没有设计出更好的算法。
[编辑] 族线、种子和同族数
Jason Doucette杜撰的术语族线（thread）指的是在逆序相加迭代中产生的那些可能或不能形成回文数的那些数组成的序列。对任意给定的种子（seed），它都可和它的同族数（kin numbers）汇聚到相同的族线上。族线不包括最初的种子或同族数，只包括它们汇聚后的序列中共有的那些数。
种子是利克瑞尔数的一个子集，它是这个非回文数的产生族线中最小的那个数。种子本身可能是个回文数。上面的列表中用粗体显示了前三个例子。
同族数也是利克瑞尔数的子集，它包含了族线中除种子及任何能经一次迭代后汇聚于给定族线的数之外的所有其它数。该术语是由Koji Yamashita 在 1997 年引入的。
[编辑] 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 把他的发现连同最后的检查点文件一起发布在互联网上，并邀请其他人一起用得到的这个大数继续寻找回文数。
1995年，Tim Irvin担起了这个挑战，并在三个月里用一台超级计算机计算到了两百万位以上，其间也未出现回文数的结果。Jason Doucette继而加入，并在2000年5月计算到了 12,500,000 个数位。Wade VanLandingham使用 Jason Doucette 的程序计算到 1,300 万位，这成为加拿大少儿科学杂志上发表的一项纪录。从2000年6月起，Wade VanLandingham 成为领军人，他使用多位发烧友编写的不同程序，到 2005年7月26日，VanLandingham 已经计算到了2亿6千3百万位以上（以每5到7天一百万位的速度）。这之间的结果中仍未出现回文数。
其它基于使用同样的重复逆序相加的暴力测试法而可能是利克瑞尔数的数还有 879, 1997, 7059 和 9999，对它们已进行了数百万次迭代而未在结果中发现回文数. [6]
[编辑] 外部链接
- 196 及其它利克瑞尔数 by Wade VanLandingham
- Benjamin Despres
- Jason Doucette - 世界纪录 - 196 回文数探索，最终产生回文数中迭代次数最多的
- John Walker - 历时三年的计算
- Tim Irvin - 关于历时两个月的计算
