新浪博客

寻觅“十全十美”数

2024-08-04 16:08阅读：

http://blog.sina.cn/dpool/blog/u/1607750864

寻觅“十全十美”数
寻觅“十全十美”数
有湖北武汉读者瞿**求问，他和一批编程爱好者想找出具有“十全十美”性质的数。这样的每一个数都包含0～9这十个数字(这就是所谓的“十全”)，同时还能够一个不拉地被1～10这十个数字分别整除(这就是所谓的“十美”)。可是找了很长的时间，花了不少的精力来计算，至今没有找到任何一个这样的“十全十美”的数字。这位瞿**问林老师，世界上存在这样的“十全十美”的数字吗？下面是林老师的回答。
首先不要小看了找“十全十美”数字这样的“数字游戏”。许多大数学家，像高斯、欧拉、哥德巴赫、哈代、华罗庚等人都曾经花了不少的精力来研究数字中隐藏的规律来玩类似的“数字游戏”。有一些“数字游戏”的背后实际上隐藏着重要的数学命题。所以花一点时间来研究“数字游戏”还是有价值的。
其次，经过认真的研究，林老师发现“十全十美”数字是真实地存在的。经过编程计算共有11461个“十全十美”数。看起来“十全十美”数字有一万多个相当多，但是如果仅仅靠笔算来找真是太困难了。符合“十全”条件的十位数超过9877亿个：
9876543210-1023456789=987741975311
而这其中仅仅有11461个符合条件，靠笔算漫无目标地去找，平均在861万多个10位数中仅仅有那么一个“十全十美”数，可见单纯靠笔算哪怕是
找到一个“十全十美”数，也是极其困难的。难怪武汉的瞿**费了许多时间都没有结果。
但是靠计算机编程，在优化了计算方法的前提下，几个小时就能完成全部计算(在使用FMSLogo或MSWLogo编程的情况下15843秒——约合4.4个小时就计算完毕了)。
即便是使用计算机编程，如果不优化计算方法，整个计算时间也可能长得根本受不了(例如几个星期、几个月)。优化计算的思路如下：
A. “十全十美”数既然能够被10整除，那么末位一定是0，根本用不着计算用不着“找”。这么一个数位不用找，整个计算量就缩小为原来的十分之一！
B. 末位是0，那么这个数字一定能够被2和5整除。这样计算量又进一步减少。
C. 从整个十位数字来看，末位是0的数字，如果要被4整除，那么倒数第二位数只能是偶数(是2、4、6、8)。这样的思路在编程上体现为：
for[a9 2 8 2][ ]
D. 这样子筛选下来“十全”数字只要还能够被7、8、9三个数字整除，那么这个“十全”数就一定是“十美”数字了。可能还存在其他进一步优化节省计算工作量的途径，请大家一起来想办法。
E. 我们用a1～a9九重循环产生前9位数字，末位加上0，就有10位数字了。但是这样组合出来的数字非常可能有重复的数字——也就不是“十全”数字。这时用remdup命令去掉任何重复的数字，经此处理后用count命令检测数字的长度，如果还是10位数，那就是“十全”数。但是随便一个“十全”数字并不一定都是“十美”数。现在如果能够被7、8、9都整除，那就确确实实找到了一个“十全十美”数。
F. 这显然是一个计算时间极为冗长的程序。我们用timemilli记录时间，每找到100个“十全十美”数就显示输出已经用掉的时间是多少秒钟，都计算完毕了输出“全程计算时间”。每台计算机需要的时间可能都不一样——这和你的计算机的CPU算力、内存的大小等因素有关。
还能进一步优化程序算得更快一些吗？我们共同努力吧！现有的源程序及计算结果如下：


源程序：
to zc10 ;十全十美10位数
make 't0 timemilli ;开始时间毫秒计数
make 'n 1 ;符合条件的十全十美数计数器
for[a1 1 9][ ;产生第1-第8位数的数字
for[a2 1 9][
for[a3 1 9][
for[a4 1 9][
for[a5 1 9][
for[a6 1 9][
for[a7 1 9][
for[a8 1 9][
for[a9 2 8 2][
;因为能够被4整除所以倒数第2个数字是2468
make 's (
;将各位数字组合成10位数，末尾是0所以能被10整除
word :a1 :a2 :a3 :a4 :a5 :a6 :a7 :a8 :a9 '0)
make 'ss remdup :s ;去掉重复数字后的数赋值给:SS
if 10=count :ss[
;如果:SS还是10位数说明是十全数字
make 'flag 0 ;能否被1-10整除的标志位先赋值0
for[i 7 9][
;如果能被789都整除那么就能被1-10整除
if :ss/:i=int(:ss/:i)[make 'flag :flag+1]]
if :flag=3[ ;:flag=3说明这是个10美数
make 'n :n+1 ;十全十美数的计数增长1
(pr :n :ss) ;输出这个十全十美数
if :n/100=int(:n/100)[
;十全十美数每满100个就测算耗费的时间
make 't1 timemilli
(pr '-----当前耗时 (:t1-:t0)/1000 '秒)]]]

]]]]]]]]]
make 't1 timemilli ;计算终了，输出总共花了多少时间。
(pr '全程计算时间 (:t1-:t0)/1000 '秒)
end


计算结果：
ZC10
2 1234759680
3 1234857960
4 1234895760
5 1234958760
6 1235487960
7 1235679480
8 1235976840
……
97 1283957640
98 1284375960
99 1284539760
100 1284753960
-----当前耗时 365.588 秒
……
11397 9853472160
11398 9853671240
11399 9853721640
11400 9853724160
-----当前耗时 15549.197 秒
……
11451 9874123560
11452 9874156320
11453 9874312560
11454 9874325160
11455 9874635120
11456 9875164320
11457 9875416320
11458 9875421360
11459 9875643120
11460 9876134520
11461 9876351240
全程计算时间 15843.789 秒
寻觅“十全十美”数
寻觅“十全十美”数
寻觅“十全十美”数
LOGO编程动画：
寻觅“十全十美”数

我的更多文章

下载客户端阅读体验更佳

APP专享