自分自身を含まない約数の和がちょうど自分自身と等しくなる数を完全数と呼 ぶ。例えば28の場合、自分自身を含まない約数の和は1+2+4+7+14=28となり、 28が完全数であることがわかる。
自分自身を含まない約数の和が自分自身より小さいものは不足数と呼び、自分 自身より大きいものは過剰数と呼ぶ。
12は一番小さい過剰数で、1+2+3+4+6=16となる。二つの過剰数の和で一番小さ いものは24である。数学的な解析により、28123より大きな全ての整数は二つの 過剰数の和で表せることがわかっている。一方で、二つの過剰数の和として表 せない最大の数はこの上限より小さいことがわかっているにもかかわらず、解 析的にはこれ以上この上限を下げることはできない。
二つの過剰数の和として表すことができない全ての正の整数の和を求めよ。
まず過剰数の無限リストをabundantsとして定義する。1からの自然数に対して 自分自身を含まない約数の和が自分自身より大きいかどうかでチェックし filterをかける。28123以上の数は全て二つの過剰数の和で表せることがわかっ ているので、1から28123までの数に対して二つの過剰数の和で表せるかをチェッ クし、表せないものの和を求めれば答えが求まる。
ここで二つの過剰数の和で表せるかをチェックする関数をnotSumとする。チェッ クする対象の数より小さい過剰数のリストを取り出しasとする。対象の数から asのそれぞれの要素を引いた答えがasの要素の中にあれば、それは対象の数が 二つの過剰数の和で表せるとわかる。intersectは二つのリストの共通要素を求 める関数なのでこれを用いて求めることができる。この方法は非常に遅いがと りあえず解が求まったので今回はこれでよしとする。
abundants = filter (\n -> (sum $ properFactors n) > n) [1..]
euler023 = sum $ filter notSum [1..28123]
where notSum n = intersect (map (n -) as) as == []
where as = takeWhile (< n) abundants