利克瑞尔数

利克瑞尔数（Lychrel Number）是将一个数字和该数字的各数位逆序排列后形成的新数相加，并将此过程反复迭代后，最终形成的一个非回文数的自然数。其名称“利克瑞尔（Lychrel）”由Wade VanLandingham将他的女友Cheryl的名字经字母换位所得出。[1]

在1至1,000,000的数字里，已知有122962个数字不能产生回文数字。

逆序相加的过程

逆序相加是将一个自然数的各位逆序排列后再与原数相加，得到两者之和。例如： 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（英语：Jason Doucette）的算法及程序（程序使用的是Benjamin Despres的逆序相加代码）于2005年11月30日发现。

从0开始能找到的第一个看起来（但尚未证实）不能形成回文数的数是196，它（被认为）是最小的利克瑞尔数。

族线、种子和同族数

Jason Doucette（英语：Jason Doucette）杜撰的术语族线（thread）指的是在逆序相加迭代中产生的那些可能或不能形成回文数的那些数组成的序列。对任意给定的种子（seed），它都可和它的同族数（kin numbers）汇聚到相同的族线上。族线不包括最初的种子或同族数，只包括它们汇聚后的序列中共有的那些数。

种子是利克瑞尔数的一个子集，它是这个非回文数的产生族线中最小的那个数。种子本身可能是个回文数。上面的列表中用粗体显示了前三个例子。

同族数也是利克瑞尔数的子集，它包含了族线中除种子及任何能经一次迭代后汇聚于给定族线的数之外的所有其他数。该术语是由Koji Yamashita在1997年引入的。

尚未证实的结论

在其他基数下，某些数可被证明经重复的逆序相加迭代后无法形成回文数，例如二进制中的10110。[1] 但对于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（英语：Jason Doucette）、Ian Peters（英语：Ian Peters）和Benjamin Despres制作的计算机程序已经发现了其他（可能的）利克瑞尔数。实际上，Benjamin Despres的程序能辨别出目前已测试出的从1位数到16位数之间每种数位长度的利克瑞尔种子数。[2] Wade VanLandingham的站点列出了发现的不同位数的利克瑞尔种子数的总数。[3]

对196的探索

由于196（十进制）可能是最小的利克瑞尔数，因而它受到了最多的关注。

1987年8月12日，John Walker（英语：John Walker (programmer)）在一台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把他的发现连同最后的检查点文件一起发布在互联网上，并邀请其他人一起用得到的这个大数继续寻找回文数。

John Walker最初实施的暴力测试法经过了改良以更好地利用迭代的优点。例如，Vaughn Suite设计了一个程序仅保存每次迭代结果的开头和末尾的一些数位，这样就能在进行上百万次迭代时不必每次将整个迭代结果保存到文件中（如果不是回文数，通常只对比开头和末尾的若干位就能确定。在迭代结果是很大的数时，如果数字太多则必须要使用磁盘文件进行辅助存储就会严重影响迭代速度，这样做则可避免这种影响，仅在保存的那些位完全相符时才须作进一步测试）[4] 。

1995年，Tim Irvin和Larry Simkins担起了这个挑战，在三个月里用一台超级计算机计算到了两百万位以上，其间也未出现回文数的结果。Jason Doucette（英语：Jason Doucette）继而加入，并在2000年5月计算到了1250万位。Wade VanLandingham使用Jason Doucette的程序计算到1,300万位，这成为加拿大少儿科学杂志上发表的一项纪录。从2000年6月起，Wade VanLandingham成为领军人。通过使用多位发烧友编写的不同程序，VanLandingham达到了每5到7天一百万次的迭代速度。到2005年7月26日，VanLandingham已经计算到2亿6千3百万位以上。2011年Romain Dolbeau使用分布式计算完成了十亿次迭代，生成了413,930,770位的数字。2015年2月，他的计算结果达到了十亿位数，但这之间的结果中仍未出现回文数。

迄今为止，对逆序相加迭代过程还没有设计出较好的算法。

其他基于使用同样的重复逆序相加的测试法而可能是利克瑞尔数的数还有879, 1997和7059，对它们已进行了数百万次迭代而未在结果中发现回文数. [5]

特定进制中可能的最小利克瑞尔数

（可能的）利克瑞尔数在不同的进制中也存在，以下列出一些进制中可能是利克瑞尔数的最小数字 （OEIS数列A060382）:

进制 可能的最小利克瑞尔数 10进制表示
2 10110 22
3 10201 100
4 3333 255
5 10313 708
6 4555 1079
7 10513 2656
8 1775 1021
9 728 593
10 196 196
11 83A 1011
12 179 237
13 CCC 2196
14 1BB 361
15 1EC 447
16 19D 413
17 B6G 3297
18 1AF 519
19 HI 341
20 IJ 379
21 1CI 711
22 KL 461
23 LM 505
24 MN 551
25 1FM 1022
26 OP 649
27 PQ 701
28 QR 755
29 RS 811
30 ST 869

外部链接

参考文献

  1. ^ FAQ. [2020-08-10]. （原始内容存档于2006-12-01）.