Project Euler 第12問

Q.

三角数の数列は自然数の和で表わされ, 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個より多く約数をもつ最初の三角数はいくつか.

A.

ｎ番目の三角形の数列が幾つになるかをもとめる関数を作って、ある数の約数がいくつあるかを返す関数と組み合わせてそれが500を超えるｎを求める。

実直に下記のコードを書いて実行したら終わらない

def n_yakusu(n)

y=0

for i in (1..n/2)

y += 1 if n % i ==0

end

return y+1

end

n=1

loop do

triangle = n*(n+1)/2

break if n_yakusu(triangle) > 500

puts n if n % 100 == 0

n += 1

end

puts n

指定された数字を素因数に分解するprimeライブラリの関数を使い、尚且つ因数を例えば１２なら2**2+3**1と分解できるのだが上記ライブラリーの答え[[2,2],[3,1]]と約数の個数が答えの乗数に１を加えたものの積になるという知識をネットで貰って説いたら極めて高速だった。答えは下記でn=12375を得た　三角形ならば76,576,500になる

require 'prime'

def n_yakusu(n)

return 2 if Prime.prime?(n)

su=1

Prime.prime_division(n).each do |e|

su *= (e[1]+1)

end

return su

end

n=1

loop do

triangle = n*(n+1)/2

#puts n.to_s + ' : ' + (n*(n+1)/2).to_s

break if n_yakusu(triangle) > 500

puts n.to_s + ' , ' + n_yakusu(triangle).to_s if n % 100 == 0

n += 1

end

puts n