Project Euler 38,39

Problem 38

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

nで分ける。そのとき左辺第一項をmとして、mの範囲が決まる。例えば、n=4なら、右辺は最初の2つは3桁で残りは2桁だから、

2m ≥ 100, 3m < 100 => 34 ≤ m ≤ 50

range n = if k < n then [div (10^m + k) (k + 1) .. div (10^m - 1) k]
                   else [10^(m-1) .. div (10^m - 1) n]
                where
                    m = div 9 n
                    k = n * (m + 1) - 9

digits 0 = []
digits n = (digits (div n 10)) ++ [mod n 10]
is_pan a = (foldr (\x y -> y + 2^x) 0 a) == 2^10 - 2
numerize a = foldl (\x y -> x * 10 + y) 0 a

a = concat [ [ [ m * k | k <- [1..n] ] | m <- range n ] | n <- [2..9] ]
b = filter is_pan (map (\e -> concat (map digits e)) a)
main = print(foldr max 0 (map numerize b))

Problem 39

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

ピタゴラス数の生成公式を使う。素因数分解すれば簡単に個数が分かる。

import Data.Array

sieve f p | f!p == 1  = sieve (f // [ (m, p) | m <- a, f!m == 1 ]) (p + 1)
          | p * p > n = f
          | otherwise  = sieve f (p + 1)
                where a = if p == 2 then [p*2,p*3..n] else [p*3,p*5..n]

n = 1000
f = sieve (array (2, n) [ (k, 1) | k <- [2..n] ]) 2

div_pow n p | mod n p /= 0 = (n, 0)
            | otherwise    = (\(n, e) -> (n, e + 1)) (div_pow (div n p) p)

factorize 1 = []
factorize n | f!n == 1  = [ (n, 1) ]
            | otherwise = [(p, e)] ++ (factorize m)
                where
                    p = f!n
                    (m, e) = div_pow n (f!n)

divs [] = [1]
divs ((p,e):fs) = [ p^e1 * n | e1 <- [0..e], n <- (divs fs) ]
d = divs . factorize

d3 m = concat (map (\(p,r) -> [ (p,q,div r q) | q <- d r ])
                                (map (\p -> (p, div m p)) (d m)))
is_valid_triplet (_,m,n) = 
        (mod n 2) == 1 && m < n && n < m * 2 && gcd m n == 1
count_Pythagoras m = length (filter is_valid_triplet (d3 (div m 2)))
greater x y = if snd x >= snd y then x else y
a = foldl1 greater [ (k, count_Pythagoras k) | k <- [2,4..n] ]
main = print(fst a)