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