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 0) :  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
から