約数の個数を求める - Project Eulerの数学
「Project Eulerの数学」としての第一弾として、約数の個数を求めたい。
数学的に厳密な証明ではなく、読んで納得できるような説明を目指したい。
自然数nが、素数2のべき乗で表せる場合
まず1については、約数は1のみであり、約数の個数は1となる。
2については、約数は1と2であり、約数の個数は2となる。ここで、2の仲間として、1, 2, 4, 8, 16, ... について考えたい。
| n | nの約数 | nの約数の個数 |
|---|---|---|
| 1 = 20 | 1 | 1 |
| 2 = 21 | 1, 2 | 2 |
| 4 = 22 | 1, 2, 4 | 3 |
| 8 = 23 | 1, 2, 4, 8 | 4 |
| 16 = 24 | 1, 2, 4, 8, 16 | 5 |
つまり、n = 2a のとき、nの約数の個数は(a+1)個となっている。
2のべき乗の約数は、全て2のべき乗である。
約数を2bと表すと、bは、0 <= b <= a の範囲なので、約数の個数は(a + 1)個となる。
自然数nが、3以上の素数のべき乗で表せる場合
次は3の仲間として、1, 3, 9, 27, 81, ... について考える。
| n | nの約数 | nの約数の個数 |
|---|---|---|
| 1 = 30 | 1 | 1 |
| 3 = 31 | 1, 3 | 2 |
| 9 = 32 | 1, 3, 9 | 3 |
| 27 = 33 | 1, 3, 9, 27 | 4 |
| 81 = 34 | 1, 3, 9, 27, 81 | 5 |
基数が3の場合も、n = 3a のとき、nの約数の個数は(a+1)個と表せる。
他の素数、5, 7, 11, ... についても同様であるので、一般化すると、素数 p について、n = pa のとき、nの約数の個数は(a+1)個となる。
自然数nが、合成数の場合
2つの素数の積について考えよう。nが6のとき、1, 2, 3, 6 がその約数であり、1、1に2か3のどちらかをかけたもの、1に2か3の両方をかけたもの、となる。
6の約数
| 20 | 21 | |
|---|---|---|
| 30 | 1 = 20 * 30 | 2 = 21 * 30 |
| 31 | 3 = 20 * 31 | 6 = 21 * 31 |
同様に、36については、次のように表せる。
36の約数
| 20 | 21 | 22 | |
|---|---|---|---|
| 30 | 1 = 20 * 30 | 2 = 21 * 30 | 4 = 22 * 30 |
| 31 | 3 = 20 * 31 | 6 = 21 * 31 | 12 = 22 * 31 |
| 32 | 9 = 20 * 32 | 18 = 21 * 32 | 36 = 22 * 32 |
36の約数を素因数分解し、2に着目すると、素因数に2を含まないもの、2を1つ含むもの、2を2つ含むものの、3種類に分類できる。
もう1つの素数 3 に着目すると、素因数に3を含まないもの、3を1つ含むもの、3を2つ含むものの、3種類に分類できる。素因数分解の一意性から、これらは9個の約数に対応している。
n = 6 = 21 * 31 のとき、約数は 2a * 3b (0 <= a <= 1, 0 <= b <= 1)で表せ、2 * 2 = 4個の約数を持つ。
n = 36 = 22 * 32 のとき、約数は 2a * 3b (0 <= a <= 2, 0 <= b <= 2)で表せ、3 * 3 = 9個の約数を持つ。
まとめ
一般化すると、p, q, r, ... を素数、a, b, c を自然数として、n = pa * qb * rc * ... のとき、約数の個数は (a + 1) * (b + 1) * (c + 1) と表せる。