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 (0,m) $ map (s.divsSum) [0..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

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