この記事の所要時間： 約 1分35秒
No.12 Highly divisible triangular number
問題.
Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,
\begin{align*}
1+2+3+4+5+6+7 = 28
\end{align*}
で, 7 番目までの三角数の正の約数は, 以下のようになります.
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
正の約数の個数が 5 個を初めて超えるのは 28 です.
では, 正の約数の個数が初めて 500 個を超える三角数は?
考え方とプログラム例(Python)
正の約数の個数を求める関数
num_of_divisors()
を定義します.
約数をすべて実際に数えるのではなく, 公式を使います.
自然数 \(n\) が
\begin{align*}
n = p_1^{q_1}\cdot p_2^{q_2}\cdots p_N^{q_N}
\end{align*}
(\(p_1, \ldots, p_N\) は異なる素数)
と素因数分解されるとき,
約数の個数 num_of_divisors(n) は,
num_of_divisors(n) = \((q_1+1)(q_2+1)\cdots(q_N+1)\)
となることを利用します
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def num_of_divisors(n): Num = 1 i = 2 while n != 1: num = 1 while n % i == 0: n /= i num += 1 Num *= num i += 1 return Num n = 1 while True: Tn = n * (n + 1) / 2 if num_of_divisors(Tn) > 500: print Tn break n += 1 |
計算時間は 4.15 秒でした.
