三角数列で約数の数が500を超える最初の数を求める
まず思いつく方針は、与えられた数nに対して約数のリストを返す関数fを作り、それを三角数列のリストに対してmap (length.f)してやるというもの。ただしこれは時間が掛かる。ハッキリ言って一晩計算を回しても終わらない。(やってみた私が言うのだから間違いない)
そこで、方針を大胆に変更し、数学の知識を借りて、具体的な約数のリストは脇において与えられた数nの約数の数を返す関数を考える。以前に作った素数列生成関数primesを利用して、素数で割れるだけ割って行く。なぜそんなことをするかと言うと
という知識に頼りたいからである。これでようやく現実的な時間で計算を終えることができた。
なお、今回は Data.List.group という関数を拝借した。本当はこいつを実装してなんぼの世界だと思うのだが、難しいのと面倒(!)なのとで諦めた。またいつかどこかで挑戦しようと思う。
group を使わずに解きたかった★