累进可除数

累进可除数（）是有以下特質的整數：首個位非零，而且由它首n個位組成的數是n的倍數。

例如345654:

• 1 \mid 3
• 2 \mid 34
• 3 \mid 345
• 4 \mid 3456

而123456就非累进可除数，因為1234不是4的倍數。

累进可除数可以在不同的进位制中定義。本條目僅談論十進制中的情況。

背景
累进可除数是趣味數學上的一道名題的一般化：

:用1至9排列成一個數，使其首2個位能被2除盡，首3個位能被3除盡，如此類推，整個數是9的倍數。

雖然9位的累进可除数有2492個，但唯一一個包含1至9的數字而不重覆的只有一個，是381,654,729。

累进可除数的數目
若k是n - 1位的累进可除数，若有10k和10k + 9之間有數可以被k整除，k便可以擴充一個位，成為n位的累进可除数。若n \le 10，必定可以由n-1位的累进可除数擴充成n位的累进可除数，且有多於一個可行的擴充辦法。反之，若n > 10，n越大，能夠擴充成為另一個累进可除数的辦法隨之而越少。因此，將累进可除数的分布畫成曲線圖，會得出一條鐘形曲線。

平均來說，每個n - 1位的累进可除数擴充成n位的累进可除数有\frac{10}{n}種方法。這產生了以下這條用以估計n位的累进可除数數目的公式（以F(n)表示n位累进可除数的數目）：
:F(n) \approx \frac{9 \times 10^{n - 1}}{n!}

將所有n之值加起來套入此式，就得出所有累进可除数的數目：

:\frac{9(e^{10} - 1)}{10} \approx 19823

最長的累进可除数有25位，等於360,852,885,036,840,078,603,672,5。

相關問題

• 在泛位數中數字0~9各出現一次的累進可除數，唯一的解是381,654,729,0
• 在累进可除数上的數字運用加上限制。例如：求最長的累进可除数其數字均為偶數。答案是480,006,882,084,660,840,40。
• 找尋回文累进可除数。這類數最長的是300,006,000,03。
• 找出其他進位制中的累进可除数。

外部連結

• [http://jwilson.coe.uga.edu/emt725/Class/Lanier/Nine.Digit/nine.html Nine Digit Number] (英文)
• [http://www.bitman.name/math/article/1204/] (意大利文)