プロジェクトオイラー12.

この記事の所要時間: 151

No.12 Highly divisible triangular number

問題.

Q. 三角数 とは, 1 からの連続した自然数の和で表される数です. 例えば 7 番目の三角数は,

\begin{equation*} 1+2+3+4+5+6+7 = 28 \end{equation*}

で, 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{equation*} n = p_1^{q_1}\cdot p_2^{q_2}\cdots p_N^{q_N} \end{equation*}

(p_1, \ldots, p_N は異なる素数)

と素因数分解されるとき,

約数の個数 num_of_divisors(n) は,

num_of_divisors(n) = (q_1+1)(q_2+1)\cdots(q_N+1)

となることを利用します

計算時間は 4.15 秒でした.

答えはこの下の行にあります. 反転してください.

A. 76576500 (12375番目の三角数)

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加