Problem 110

import Number
import Data.List
import Data.Maybe

dscList lim max'
    | lim < 1 = [[]]
    | otherwise = [x:ys|x<-[1..max'],ys<-dscList (lim' x) x]
    where lim' y = lim / (2*(fromIntegral y)+1)

p110 = dscList 7999999 60

decode = product.zipWith (^) primes

main = print.minimum.map decode $ p110

少し遅いから、ちょっとやる気をだして、分枝限定法。

import Number
import Data.List
import Data.Ratio

--brunch and bounds method
bb :: Rational -> Integer -> [Integer] -> Rational-> Rational
bb obj m (p:ps) upp
   | obj < 1 = 1
   | otherwise = foldr ($) upp [((toRational p^q)*).brunch q|q<-reverse[1..bound]]
   where bound = min m .floor.log' p $ upp
         log' a b = (log.realToFrac) b / (log.realToFrac) a
         brunch r u = bb obj' r ps upp'
             where obj' = obj / (2*fromIntegral r + 1)
                   upp' = u / (toRational p^r)

main = print.numerator.bb 7999999 100 primes $ 10^30

プログラムを走らせる計算機が変わったから
単純に速度比較はできないが、間違いなく速くなった。
すくなくとも、ghci上で動くレベルになった。
100,10^30は明らかな上界値。別に60とかにしてもいいけど
計算時間はほとんど変わらない。つまり、探索範囲が大きく増えることは無い。
ちなみに、Problem 108は7999999を1999に変えればよい。