コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者: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 に対して、10k から 10k + 9 の間にある n の倍数を探せばよい。このように探すと n ≤ 10 においては常に一つ以上の多重可除数を見つけることができる。しかし n > 10 においては必ずしも見つけることができなくなり、さらに n が大きくなると多重可除数が見つからないことが多くなっていく。

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

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

この推定値は実際の値と比べて約 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

関連する問題

[編集]

多重可除数は、娯楽数学英語版における次の問題の一般化となっている。

最初の二桁が 2 の倍数、最初の三桁が 3 の倍数、最初の四桁が 4 の倍数と以下続き、最終的に数全体が 9 の倍数であるように、1 から 9 までの数字を並べ替えよ。

この問題の解答は、九桁の多重可除数に対して「1 から 9 までの数字を一つずつ含む」という制限を課したものとなる。九桁の多重可除数は全部で 2492 個存在するが、うち追加の制限を満たすものは次の一つのみである。

381654729

その他、多重可除数を含む問題には次のものがある。

  • 多重可除数に何らかの制限を課したもの。
    • 例:偶数の数字のみからなる多重可除数のうち最長のものを求めよ。(答:480 006 882 084 660 840 40
  • 回文多重可除数を求めるもの。
    • 例:最長の回文多重可除数を求めよ。(答:300 006 000 03
  • 十進法以外で多重可除数を探すもの。
    • 例:十二進法における最長の多重可除数を求めよ。(答:606 890 346 850 Ɛᘔ6 800 Ɛ03 620 646 4[1]
  • 最初に述べた問題は次のように改変できる。(同じことは他の問題でも考えられる)
    • 0 から 9 までの数字を並べ替えて 10 桁の多重可除数を作れ。(答:3816547290

脚注

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

外部リンク

[編集]