Project Euler 解答

Project Euler Problem 039

Project Euler Problem 039

import Data.List
import Data.Ord
d :: Integer
d=1000
-- 整数倍を含む原始ピタゴラス数の和のリスト
-- (m^2+n^2)+2*m*n+(m^2-n^2) = 2m(m+n)
pyt :: Integral t => t -> [t]
pyt dd=[k*l |
        m<-[2..sd],
        n<-filter (\x -> (even (m+x))&&(gcd m x==1)) [1..m],
        let l=2*m*(m+n), --lは2m^2より大きいので、mはsqrt(2/d)までで良い
        k<-[1..(dd`quot`l)]]
  where sd = ceiling (sqrt $ fromIntegral (dd`quot`2)::Double)
ans1 :: Integer
ans1 = head $ maximumBy (comparing length) $ group $ sort $ pyt d
-- 840
main :: IO ()
main = print ans1

-- http://en.wikipedia.org/wiki/Pythagorean_triple
-- 上の式で、原始ピタゴラス数はこの時に得られる
-- (m,n)が互いに素
-- |m - n|が奇数

since 2013