問題をこなしていく中で自分用のProject Euler ユーティリティライブラリzaneli-eulerもブラッシュアップされてきて
いい感じだ。
Problem 49 補足
こちらのコメントを元に書き換えてみた。
mを[1..(9999-n) `div` 2]から[2,4..(9999-n) `div` 2]と偶数に限定した。
nが素数(2以外奇数)なのでこれに奇数を加算するとn2が偶数になり、素数とは成り得ないため。

また、find (not . null) $ map ... primesしてfromJustしていた所を>>=で書き換える。
おお、随分簡潔になった。
特にfromJustなんかは書くと負けたような気になるので、このような書き方ができるのを知れたのは良かった。
なかなか自分で書いていると出てこない発想だった…。
Problem 50 補足
こちらは教えてもらった解法がなかなか飲み込めず苦戦した…。
これとかこれとかこれとかこれとかこれとかこれとか。
…うーむ、しかし何がどうなっているのかいまいち理解が追いつかない。
limit=10の時にどのように動くのか、細かい処理に切り出して読み解いていこう。
まずはscanl (\(n,xs) x -> (n + x, tail xs)) (0, primes) primesの部分。
0と[2,3,5,7]のペアを出発点として、リストのheadから順にxにscanlで加算していく。
[(0,[2,3,5,7]),(2,[3,5,7]),(5,[5,7]),(10,[7]),(17,[])]こんなリストができる。
これをreverseして[(17,[]),(10,[7]),(5,[5,7]),(2,[3,5,7]),(0,[2,3,5,7])]こう。
これは、「2からある項までの素数の合計」と「合計した素数の次の項からの素数のリスト」のペアを作っている。
これにfを適用していく。
(x, ns) = (5,[5,7])のとき、まずzip primes xsを適用して[(2,5),(3,7)]
これは「2から始まる素数」と「ある時点から始まる素数」のペアを作っている。
そこに(\s (x, y) -> s - x + y)つまり、「2からある項までの素数の合計」から
ペアのfstを引いてsndを足す、という操作を繰り返す。
primeSums[5,8,2,3,5,7,0,0,0,0,0]となる。
こうやって連続する素数の合計を作り、その中で素数となる最初のものを探す。

…うおー、難しい!
しかし、元々1分以上かかっていたものが2~3秒で終わると、劇的な改善が!
Problem 51 補足
こういうコメントをいただいたので、zaneli-euler側も修正してこの問題に使えるようにしてみた。
Zaneli.Euler.primes関数を外部公開し、<「ある条件を満たすまで素数を追加し続け、条件を満たせば何らかの値を返す」ようにした。
今回の問題では、追加していった素数のリスト自体を返したいのではなくて、「桁を同じ数で置き換えた8つの素数」が欲しいため
search'関数をprimesの引数に渡している。
ここで得られた値がそのまま解であればいいのだが、(そして今回の場合はその通りではあるのだが)
ちょっと考えなくてはいけない。
解として「最小の素数」が求められているが、2,3,5...と小さい値から順に素数を作りつつ条件に合うかを探していく中で、
仮に「28881」が条件を満たした場合、[21111, 22221, 23331, 24441, 25551, 26661, 27771, 28881]が得られ
「21111」が解となってしまうが、
この時点でまだ調べていない「19991」も条件を満たすとすれば、最小の素数は「11111」である可能性がある。
そこで、かなり無駄な処理ではあるが、一度primes search'で得られた値と同一桁の最大値まで調べきるため
再度primesLimitNumで素数を作ってsearch'を満たすものを探すことにした。
ただし最初にprimes search'で得られた値以降には条件を満たすものはないので、takeWhile (\ps -> (fst ps) >= p) ps''して
primes search'で得られた値~同一桁の最大値」までを再実行していることになる。
何だか理論も実装も無理矢理感のあるものになってしまったが、それでもeuler51-1.hsで5分以上かかりお手上げ状態だったのに比べ、
20秒程度で完了するのでまぁ良しとするか…。

Copyright© 2011-2021 Shunsuke Otani All Right Reserved .