「HaskellでProject Euler(Problem 64～66)」ブログ用

euler64.hs

import Data.List (unfoldr)

main = print $ length $ filter (odd . length . snd . sqrts) [1..10000]

sqrts :: Integer -> (Integer, [Integer])
sqrts n | m^2 == n  = (n, [])
        | otherwise = (m, unfoldr f $ (1, -m, Nothing))
  where
    m = truncate $ sqrt $ fromInteger n
    f (x, y, Just z) | (x, y) == z = Nothing
    f (x, y, z)                    = Just (q, (x', r-m, termCond z))
      where
        x' = (n - (y^2)) `div` x
        (q, r) = ((negate y)+m) `divMod` x'
        termCond Nothing = Just (x, y)
        termCond _       = z

euler65.hs

import Data.Ratio ((%), numerator)
import Zaneli.Euler (numToList)

main = print $ sum $ numToList $ numerator $ convergent $ map (%1) $ take 100 es

es :: [Integer]
es = 2:concatMap (\n -> [1, n, 1]) [2,4..]

convergent :: Fractional a => [a] -> a
convergent ns = foldr1 (\a b -> a + recip b) ns

euler66.hs

import Data.List (find, inits, maximumBy, unfoldr)
import Data.Maybe (mapMaybe)
import Data.Ord (comparing)
import Data.Ratio ((%), denominator, numerator, Ratio)

main = print $ fst $ maximumBy (comparing snd) $ mapMaybe f [1..1000]
  where
    f n = fmap (\p -> (n, numerator p)) (pell n)

pell :: Integer -> Maybe (Ratio Integer)
pell d = find isPell $ map convergent ns
  where
    isPell n = (numerator n)^2 - (denominator n)^2 * d == 1
    ns | null ms   = []
       | otherwise = map (m:) $ tail $ inits $ cycle ms
      where (m, ms) = sqrts d

sqrts :: Integer -> (Integer, [Integer])
sqrts n | m^2 == n = (n, [])
        | otherwise = (m, unfoldr f $ (1, -m, Nothing))
  where
    m = truncate $ sqrt $ fromInteger n
    f (x, y, Just z) | (x, y) == z = Nothing
    f (x, y, xs)                   = Just (q, (x', r-m, termCond xs))
      where
        x' = (n - (y^2)) `div` x
        (q, r) = ((negate y)+m) `divMod` x'
        termCond Nothing = Just (x, y)
        termCond _       = xs

convergent :: Integral a => [a] -> Ratio a
convergent ns = foldr1 (\a b -> a + recip b) $ map (%1) ns