Project Euler - Problem 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 個以上の約数をもつ最初の三角数はいくらか。

まったく知らなかったですが、

n = a^q * b^q * c^r (n: 整数) ならば
n の約数の個数は (p+1)(q + 1)(r + 1)

だそーです。
普通に約数のリストを作ってその size を取るとかだとパッと終わらない。

require 'prime'

def n_aliquots(x)
  x == 1 ? 0 : x.prime_division.map{|a| a[1].succ }.inject(:*)
end

def triangulars(start = 1, stop = 1 / 0.0)
  return enum_for(__method__, start, stop) unless block_given?
  start.upto(stop){|n| yield(n * n.succ / 2) }
end

p triangulars(8).find{|n| n_aliquots(n) >= 501 }
# => 76576500