Problem 108

http://projecteuler.net/index.php?section=problems&id=108

1/a+1/b=1/n

ですが、b=n+b’と書き換えると

n^2がb’で割り切れることが分かる。

従って、n^2が1999個の約数を持つ最小のnを探せばよい。

import Number
import Data.List
import Data.Maybe
descending xs = and . zipWith (>=) xs $ tail xs
succ' (n+1) xs = let (ys,z:zs) = splitAt n xs
in ys++[z+1]++zs
next n (Just xs) | descending ys = Just ys
| otherwise = Nothing
where ys = succ' n xs
p108 = Just (replicate 7 ) :  foldr1 mergeMaybe [map (next n) p108|n<-[1..7]]
where mergeMaybe (Just u:us) (Just v:vs )
| decode u == decode v = Just u : mergeMaybe us vs
| decode u < decode  v = Just u : mergeMaybe us (Just v:vs)
| decode u > decode  v = Just v : mergeMaybe (Just u:us) vs
mergeMaybe (Just u:us) (Nothing:vs) = Just u: mergeMaybe us vs
mergeMaybe (Nothing:us) (Just v:vs) = Just v: mergeMaybe us vs
mergeMaybe (Nothing:us) (Nothing:vs) = Nothing:mergeMaybe us vs
decode = product.zipWith (^) prime
where prime = take 7 primes
main = print.decode.fromJust.find over.catMaybes$p108
where over xs = 1999 < (product.map (x->2*x+1) )xs

イメージとしてはハミング数と同じ。

最小を探すので、降順の条件を入れると、探索範囲がぐっとせまくなる、ような気がする。

mergeMaybeの実装に手間取った。

素数7で十分な理由は

7>log 1999 / log 3

から