利用者:Flightbridge/sandbox/多重可除数

（en:polydivisible number oldid=734949390）

{@{暫定記事名|date=2016年9月}}

多重可除数（英: Polydivisible number）とは、先頭 $n$ 桁が $n$ の倍数となっている数のことを言う。多重可除数は任意の基数において定義することができる。この記事では特に十進法におけるものについて扱う。

例

例として、345654 は 3, 34, 345, 3456, 34565, 345654 がそれぞれ 1, 2, 3, 4, 5, 6 の倍数なので多重可除数である。一方、123456 は 1234 が 4 の倍数でないので多重可除数でない。

多重可除数: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 102, 105, 108, 120, 123, 126, 129, 141, 144, 147, 162, 165, 168, 180, 183, 186, 189, ... オンライン整数列大辞典の数列 A144688

$n$ 桁の多重可除数のうち最小のもの: 1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640, 10200056405, 102006162060, 1020061620604, 10200616206046, 102006162060465, 1020061620604656, 10200616206046568, 108054801036000018, 1080548010360000180, 10805480103600001800, ... オンライン整数列大辞典の数列 A214437

$n$ 桁の多重可除数のうち最大のもの: 9, 98, 987, 9876, 98765, 987654, 9876545, 98765456, 987654564, 9876545640, 98765456405, 987606963096, 9876069630960, 98760696309604, 987606963096045, 9876062430364208, 98485872309636009, 984450645096105672, 9812523240364656789, 96685896604836004260, ... オンライン整数列大辞典の数列 A225608

数え上げ

$n$ 桁の多重可除数の個数 $F (n)$ は次のようになる。

9, 45, 150, 375, 750, 1200, 1713, 2227, 2492, 2492, 2225, 2041, 1575, 1132, 770, 571, 335, 180, 90, 44, 18, 12, 6, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... オンライン整数列大辞典の数列 A143671

多重可除数は全部で 20,456 個存在する。うち最も桁数が多いのは、次に示す 25 桁のものである。

3 608 528 850 368 400 786 036 725

$F (n)$ の推定

$n$ 桁の多重可除数を見つけるには、 $n - 1$ 桁の多重可除数 $k$ に対して、 $10 k$ から $10 k + 9$ の間にある $n$ の倍数を探せばよい。このように探すと $n \leq 10$ においては常に一つ以上の多重可除数を見つけることができる。しかし $n > 10$ においては必ずしも見つけることができなくなり、さらに $n$ が大きくなると多重可除数が見つからないことが多くなっていく。

$n - 1$ 桁の多重可除数 $k$ から見つかる $n$ 桁の多重可除数の個数の平均を考える。これは、 $10 k$ から $10 k + 9$ までの 10 個の数に存在する $n$ の倍数の個数の平均に等しいので、平均 $10/ n$ 個である。加えて最上位にくる数字は 0 を除く（即ち 9 種類）ことに注意すると、次のように $F (n)$ を推定することができる。

F(n)\approx 9\times {\frac {10}{2}}\times {\frac {10}{3}}\times \cdots \times {\frac {10}{n}}={\frac {9}{10}}\cdot {\frac {10^{n}}{n!}}

この $F (n)$ の総和をとることで、多重可除数の総数が近似的に求まる。

\sum _{n=1}^{\infty }F(n)\approx {\frac {9}{10}}\sum _{n=1}^{\infty }{\frac {10^{n}}{n!}}={\frac {9}{10}}(e^{10}-1)\approx 19823

この推定値は実際の値と比べて約 3% 小さい値となっている。

桁数 $n$	$F (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

桁数 $n$	$F (n)$	$F (n)$ （推定値）
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

桁数 $n$	$F (n)$	$F (n)$ （推定値）
21	18	17
22	12	8
23	6	3
24	3	1
25	1	1

脚注

^ 10 と 11 を、それぞれ 2 と 3 を半回転させた記号で表している。詳しくは十二進法#十二進法の推進を参照。

外部リンク

[1] 10 と 11 を、それぞれ 2 と 3 を半回転させた記号で表している。詳しくは十二進法#十二進法の推進を参照。

[1]

例

数え上げ

F(n) の推定

関連する問題

脚注

外部リンク

$F (n)$ の推定