Problem 95

単純な全探索、遅すぎる。

import Number
import Data.List
divsSum x = (flip(-)x).product.map f.group.factors$x
where f ps@(p:_) = let n = genericLength ps + 1
in (p^n-1)`div` (p-1)
chain m = chain' [] . iterate divsSum
where chain' xs (y:ys)
| y > m  = []
| y == 1 = []
| elem y xs = dropWhile (/=y) xs
| otherwise = chain' (xs++[y]) ys
p095 m = maximum[(length xs,minimum xs)| xs <-map (chain m)[1..m],not(null xs)]
main = print.p095$10^6

Arrayを使って、計算結果を再利用。この問題はArrayを使いやすい。ほとんど変更なしでArrayを導入。

import Number
import Data.List
import Data.Array
divsSum x = (flip(-)x).product.map f.group.factors$x
where f ps@(p:_) = let n = genericLength ps + 1
in (p^n-1)`div` (p-1)
divsSums m = listArray (,m) $ map (s.divsSum) [..m] ::Array Integer Integer
where s x | x > m = 1
| x<= m = x
chain m = chain' [] . iterate (divsSums m!)
where chain' xs (y:ys)
| y == 1 = []
| elem y xs = dropWhile (/=y) xs
| otherwise = chain' (xs++[y]) ys
p095 m = maximum[(length xs,minimum xs)| xs <-map (chain m)[1..m],not(null xs)]
main = print.p095$10^6

ちょっと速くなりました。