三角数の数列は自然数の和で生成することができる。したがって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より大きくなる最初の三角数を求めよ。
まず無限に続く三角数のリストを以下のように定義する。いろいろな書き方が できると思うが、n番目の三角数はn-1番目の三角数にnを足したものであるとい う考えでzipWithを使って定義している。次に全ての約数のリストを求める関数 factorsを定義する。1から順番に割り切れるか試している。割り切れた場合に はその数と商が約数となる。呼び出すときに余計な初期値を指定しなくてもい いようにfactorsを定義し、実際の処理はローカル関数のfactors’で行っている。
三角数のリストにmapでfactorsを適用し約数のリストのリストを求める。そし てfilterを使用して、その中から約数のリストの長さが500より大きいものをと りだし、headで最初のものを求める。求まった約数のリストの最後尾をlastで 取り出し解として表示する。アドホックであるが、約数の中で一番最後のもの が三角数そのものであることを利用している。
triangles = zipWith (+) [1..] (0 : triangles)
factors n = factors' n 1 []
where factors' n x l
| x * x > n = l
| x * x == n = x : l
| n `mod` x == 0 = x : factors' n (x + 1) ((n `div` x) : l)
| otherwise = factors' n (x + 1) l
euler012 = last $ head $ filter (\x -> length x > 500) $ map factors triangles