差が3330の等差数列、1487,4817,8147は二つの変わった点がある。1. 3つの項 全てが素数である。2. それぞれが別の項の4つの数字を並び替えたものになっ ている。
1,2,3桁の3つの素数からなる等差数列でこの性質を持っているものは存在しな いが、4桁のものはもう一つ存在する。
その3つの数字を連結した12桁の数字を求めよ。
4桁の素数の順列を求め、その中に等差数列があるかどうかをチェックするとい う方針にする。リストの中からn個の組み合わせを求める部分は他の用途でも使 えそうなので独立した関数combinationListにする。引数に指定されたリストの 要素を引数で指定された個数だけ使って組み合わせたリストのリストを返す。 例えば、ある素数の順列が4つあったときに、その中から3つをつかった数列を 作るときに使用する。
primes4は4桁の素数のリストである。そこにpermList関数をmapすることで、4 桁の素数の順列のリストを生成する。permListは対象とする数を各桁ごとに分 解し、順列を求め、数値に戻し、それが4桁の素数であるものを重複を除いて、 数値順にソートしたものである。この順列のリストから重複を除き、3以上の長 さのものについて、先のcombinationListをconcatMapすることで、3個の数列の リストを求める。concatMapはmapした結果をconcatするものである。一つの要 素に対して複数の答えを返すような関数を適用するときに、答え全体のリスト を求めるときに便利である。
最後に等差数列になっているものを関数arithでfilterして答えを求める。答え はふたつ存在し、一つは問題文で示されているもので、もう一つがこの問題の 答えとなる。
combinationList 0 _ = [[]]
combinationList 1 [x] = [[x]]
combinationList n (x:xs)
| length xs < n = [x:xs]
| otherwise = (map (x :) $ combinationList (n - 1) xs)
++ (combinationList n xs)
euler049 = filter arith $ concatMap (combinationList 3)
$ filter ((> 2) . length) $ nub $ map permList primes4
where
primes4 = takeWhile (< 10000) $ dropWhile (< 1000) primes
permList n = sort $ nub $ filter (>= 1000) $ filter isPrime
$ map listToInt $ permutation $ intToList n
arith [a, b, c] = c - b == b - a