累进可除数

累进可除数（英語：Polydivisible number）是有以下特質的整數：首個位非零，而且由它首 $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\leq 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

位數 $n$	$F(n)$	估計值
1	9	9
2	45	45
3	150	150
4	375	375
5	750	750
6	1200	1250
7	1713	1786
8	2227	2232
9	2492	2480
10	2492	2480
11	2225	2255
12	2041	1879
13	1575	1445
14	1132	1032
15	770	688
16	571	430
17	335	253
18	180	141
19	90	74
20	44	37
21	18	17
22	12	8
23	6	3
24	3	1
25	1	1

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

外部連結

Nine Digit Number （页面存档备份，存于互联网档案馆）(英文)
[1] （页面存档备份，存于互联网档案馆）(意大利文)

背景

累进可除数的數目

相關問題

外部連結