Problem 12

問題

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

英語

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) 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?

http://projecteuler.net/index.php?section=problems&id=12

日本語

三角数の数列は自然数の和で表わされ、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つ以上の約数をもつことが分る。

では、501 個以上の約数をもつ最初の三角数はいくらか。

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2012

解説

三角数の式でi番目の三角数をだす。
あとは約数の個数を求めるだけ。

ソースコード(Ruby)

require 'mathn'

i = 1
loop{
    t = i * (i + 1) / 2
    if (t.prime_division.map{|a,b|b+1} << 1).inject(:*) > 500
        p t
        exit
    end
    i+=1
}