【Project EulerにRubyで挑戦シリーズ】問12:Highly divisible triangular number

スポンサーリンク

今回の問題

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

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
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
となる.

最初の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

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

算数的な予備知識

三角数

整数を1から順に足した数のことを三角数と呼びます。

細かなことは割愛しますが、n番目の三角数は

n × (n+1) ÷ 2

で表されます。

約数の個数の算出法

ある整数の約数の個数を算出する方法ですが、
こちらも細かなことは割愛しますが、
素因数分解して得られる各素数の指数から算出することが出来ます。

例:
140 = (2の2乗)×(5の1乗)×(7の1乗)

このとき得られた指数に0乗を含むために1足して掛け算して得られる
(2 + 1)×(1 + 1)×(1 + 1) = 3×2×2 = 12
が140の約数の個数になります。

書いた内容

require 'prime'

def triangle_number(n)
  n * (n + 1) / 2
end

def divisor_count(n)
  Prime.prime_division(n).map(&:last).map{ |i| i + 1 }.inject(:*)
end

n = 2
loop do
  result = triangle_number(n)
  break if divisor_count(result) > 500
  n += 1
end

puts triangle_number(n)

三角数の算出はメソッドで分けました。

約数の個数算出もメソッドとして切り分け、Primeライブラリのprime_divisionメソッドを利用しています。

prime_divisionメソッドは[素数, 個数] の形で引数にとった値の素数を返してくれるので、個数だけの配列に整形して、算出法のとおりに1足して掛け算をしています。

これをloop文で回して、約数の個数が500を超えた時に処理を終えることで求められた値を算出しています。

※Project Eulerのリポジトリ

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。