累进可除数的再发现

luyuanhong

累进可除数的再发现

原创 大老李聊数学 大老李聊数学 2024 年 04 月 20 日 07:34 加拿大

前不久，我突发灵感，在我的微信群中发了这样一个问题：

一个整数，取最右边 1 位可被 1 整除，取最右边 2 位，可被 2 整除…取最右边 n 位，可被 n 整除。这个数最多可以写几位？除了个位数，其他位置不能有 0 。

（这个问题当然可以编程解决，但蛮力逐个搜索是不行的，还是需要一些好的算法.....）

很快，群友“离不散”发来了他/她的编程结果：

这个数字最多可以有 24 位，符合要求的 24 位数一共有 4766418 个，其中最大的一个是：

            999999996987276843378480 。

这个数字很有意思，于是我又问：

一个整数，取最左边 1 位可被 1 整除，取最左边 2 位，可被 2 整除…取最左边 n 位，可被 n 整除。这个数最多可以写几位？最大又是几？除了最高位，其他各位都可以有 0 。

很快“离不散”又发来程序运行结果，此时最大可以有 25 位，且只有一个数字符合这个要求，这个数字就是：

            3608528850368400786036725 。

于是我上网搜索了一下以上这个数字，发现原来它被称为“累进可除数”（Polydivisible number）。而第一类数字并无名称，所以我觉得第一类数字可以重新命名为“右累进可除数”，而“累进可除数”可改称为“左累进可除数”。

对左累进可除数，已经有人做了某些研究。比如对 b 进制下，n 位左累进可除数数量有如下估计公式：

             Fb(n)≈(b-1)b^(n-1)/n! 。

而实际的 10 进制下的数量与估计值也确实十分接近：



我没有看到有人研究过右累进可除数的数量，10 进制下的数量分布图如下：



另一个有意思的观察是，寻找既是左累进可除数，也是右累进可除数的数字。此时最大为 9 位数，一共有 8 个这样的数字：

186456240 , 321654240 , 369258480 , 441252720 , 648852480 , 867258720 , 882858240 , 885252240 。

它们可以叫做“双向累进可除数”！

这是一次短暂但有趣的研究经历，也佩服“离不散”群友的编程效率。你还知道哪些有意思的数字呢？欢迎留言告诉我。

大老李聊数学