互动科普

累进可除数的推广

累进可除数可以推广到把0也包括进来。形成一个十位数，要求仍维持前n位能被n整除，整个十位数能被10整除的条件。这个推广很简单：只要把0加在上述9位累进可除数的末尾就可以了，也仍然只有惟一的解。

累进可除数还可以推广到非十进制的其他进制中去。这就比较复杂了，在此不做赘述。

数学家戴维·桑格（David M. Sanger）把累进可除数进一步推广到更加一般的情况，即不要求数必须由1〜9这9个不同的数字组成，而可以用任意数字的任意组合，只要满足前n位可以被n整除这个条件。根据我们前面介绍的整除性的各种判据，显然，这样的两位数有45个，即十位上是1〜9中的任一个，个位上是0、2、4、6、8中的任一个，这样的数都可被2整除，成为两位的累进可除数。

3位的累进可除数有144个，即在以上45个两位累进可除数的基础上，每个的末尾再添加一个数，使数字根为3的倍数。例如，10的末尾加2、5、8，即102、105、108；54的末尾加0、3、6、9，即540、543、546、549等等，都是满足条件的3位累进可除数。

以此类推，位数愈多，累进可除数愈多，到9位达到最大值，有2492个，其中最小一个是102000564，最大一个是987654564，最奇特的一个是300006000。读者不妨检查一下，看看这些数是否其前两位能被2整除，前3位能被3整除，前4位能被4整除⋯⋯前8位能被8整除，整个数能被9整除。

10位的累进可除数只要在每个9位的累进可除数末尾再添加一个0就可以了，所以也有2492个。

11位的累进可除数怎么获得呢？这就需要知道怎样判定一个数能否被11整除。11整除性的判据很简单：奇数位和偶数位的数字和之差若为0或11的倍数，则该数可被11整除。这个判据的来历很简单，看一下任意数abcd的11倍的乘式就可以明白了。

由此可见，乘积的首、末位分别是a和d，中间几位分别是(a+b)、(b+c)和(c+d)。奇数位和偶数位的数字和都为（a+b+c+d）, 所以其差应该为0。判据中为什么说差是0或11的倍数呢？那是因为中间位相加可能发生进位。一旦出现进位，发生进位的位，其数字和－10（注意，因为这里是10进制），而获得进位的位+1，两者相差总是11。

好了，有了11整除性的判据，我们就可以讨论11位的累进可除数如何产生了。在2492个10位累进可除数的基础上，在每个的末尾添加0〜9中的某个数，若形成的11位数的奇数位和偶数位的数字和之差等于0或11的倍数，我们就获得了一个11位累进可除数。例如，前面提到的最小的10位累进可除数1020005640末尾添加5，在最大的10位累进可除数9876545640末尾也添加5，在非常奇特的10位累进可除数3000060000末尾则添加3，就都是11位的累进可除数。

以此类推往下做，桑格发现，位数愈多，累进可除数呈减少的趋势，到20位以后，其数量如下：

20位：有累进可除数44个。              

21位：有累进可除数18个。

22位：有累进可除数12个。

23位：有累进可除数6个。

24位：有累进可除数3个。

25位：有累进可除数一个，即3608528850368400786036725

26位及以上：不再有累进可除数。

显然，累进可除数问题可以通过计算机编程解决。在纪有奎和陈海鸣的《趣味程序设计》中就有用BASIC和FORTRAN求25位累进可除数的程序，作者宣称若有读者发现大于25位的累进可除数，可获得作者从稿费中支付的1000元发明奖。我们从前面的分析中知道，大于25位的累进可除数是不存在的，因此谁也不可能获得这笔奖金。

（本文发表于《科学世界》2011年第3期）