HaskellでProject Euler(Problem 49～51)

Project Eulerにはレベル制度的なものがあるらしく、50問解いたので晴れてLevel 2に到達した！

Problem 49. Prime permutations(素数数列)

primesで4桁の素数をまず候補として取得する。
primePermutationsでそれらの候補を初項とする条件に合致する等差数列を探す。
問題文に挙げられている1487から始まるものはまず除外して、
項差mを 1～(9999-初項)/2 として、初項にmを足した第二項がvalidなものを抽出し、
第二項にmを足した第三項もvalidなものを抽出する。
validでは与えられた数値が初項の置換で表すことができるかを調べている。
問題文から、このような条件に合致するものはもう1つだけ存在するとのことなので、
(not . null)であるものが見つかればそれを解としてよさそうだ。
見つかった3つの項を文字列にして連結して完了。
実行に時間がかかるかな、と思ったがほぼ一瞬で終わった。

Problem 50. Consecutive prime sum(連続する素数の和)

まずは愚直にこんな風に書いてみた。

import Data.List (inits, maximumBy, tails)
import Data.Function (on)
import Zaneli.Euler (isPrime, primesLimitNum)

main = print $ sum $ maximumBy (compare `on` length) $ filter (not . null) $ map search $ tails primes

limit = 1000000

primes = reverse $ primesLimitNum limit

search :: [Integer] -> [Integer]
search [] = []
search ns = maximumBy (compare `on` length) $ filter valid $ inits ns
  where
    valid xs = let x = sum xs in x < limit && isPrime x

primesの取得にreverseしているのはZaneli.Euler.primesLimitNumが逆順の数列を返すため。
searchで与えられた数列のinitsの中から和が素数になるものを抽出し、要素数が最大のものを返す。
それを、primesのtailsに対して全て行い、それらの中から要素数最大のものを解としている。
しかし、このやり方だとlimitが100,1000の時にはうまくいったが、1000000にすると処理が終わらない…。
無駄な処理が多そうだ。
そこで、このようにしてみた。

逆順の素数列に対してfを適用していく。
fはそれまでの最長の素数列の和と要素数を持っているので、
以降調べようとする素数列自体がそれまでの最長の要素数未満であれば、処理を打ち切ることができる。
そうでなければ調べようとしている素数列の中にそれまでの最長を超えるものがあるかもしれないので、
f'を適用して調べていく。
f'はそれまでの最長の素数列の和・要素数をrに保持し、それより条件を満たすより要素数が大きいものがあれば
保持しているrを書き換えながら実行していく。
isPrimeかどうかを調べる前に、それまでの最長の要素数未満である場合、和が偶数である場合(素数ではない)を
除外しており、極力無駄な処理を避けるようにしてみた。
isPrimeも、primesが逆順の素数列であることを利用してelemで前項なめなくてもいいようにしている。
これでもまだ実行に1分以上かかるが…何とか解答できた。

Problem 51. Prime digit replacements(素数の桁置換)

実は問49,問50は9月中に解いていたのだが、これはなかなか解法を思いつけず放置していた…。
というわけで約3ヶ月振り。Haskellを書くのも随分久し振りで色々忘れているな…。
散々悩んだが、これは問題文だけを見て愚直にコードに落とし込むだけでは解けない系で
素数の性質からさらに条件を絞り込む必要がありそうだった。
が、結論から言うと自力では条件の絞り込みまで導けなかった…。
こちらの記事を参考にしつつ、
1の位は置き換え対象ではなく、また置き換える個数を3に固定して条件に合致するものを探すことにした。

elem ns ["777", "888", "999"]は、
置き換える数が3つであり8つの素数が得られる場合最大値の置き換え箇所が7か8か9のいずれかとなるためこのように表している。
素数列の取得には、zaneli-euler に作成した primesLimitIndex や primesLimitNum では
あらかじめ取得したい素数の桁数か最大値か分かっていないといけないので今回の問題とは相性が悪く、
問41で使用したエラトステネスの篩を使用した素数取得関数を改良して
関数fが条件を満たして解を返すまで素数を作り続けるようにしてみた。
また、置き換えた素数の中で"000"で始まるものも許容すると
[109,111109,222109,444109,555109,666109,777109]が最初に見つかったがこれを除外するようにしている。
解き方をカンニングしてまで何とか解答できたが、これでも実行に5分以上かかる…。
もっと良いやり方があるような気がする…。