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に変えればよい。

コンテンツ