累进可除数

累进可除数（英语：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] （页面存档备份，存于互联网档案馆）(意大利文)

背景

累进可除数的数目

相关问题

外部链接