利克瑞尔数

维基百科,自由的百科全书
跳转至: 导航搜索
未解決的數學問題196是利克瑞爾數嗎? Question mark2.svg

利克瑞尔数(Lychrel Number)指的是将该数与将该数各数位逆序翻转后形成的新数相加、并将此过程反复迭代后,结果永遠無法是一个回文数自然数。“利克瑞尔”的名字是Wade VanLandingham杜撰出的,这是从他的女友Cheryl的名字经过简单的字母换位而来。 在1至1000000的數字裡,發現有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的算法及程序(程序使用的是Benjamin Despres的逆序相加代码)于2005年11月30日发现的。

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

尚未证实[编辑]

在其他基数下,某些数可被证明经重复的逆序相加迭代后肯定不能形成回文数,例如二进制中的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 DoucetteIan PetersBenjamin Despres制作的计算机程序已经发现了其他(可能的)利克瑞尔数。实际上,Benjamin Despres的程序能辨别出目前已测试出的从1位数到16位数之间每种数位长度的利克瑞尔种子数。[2] Wade VanLandingham的站点列出了发现的不同位数的利克瑞尔种子数的总数。[3]

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

族线、种子和同族数[编辑]

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,对它们已进行了数百万次迭代而未在结果中发现回文数. [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


外部链接[编辑]