projectEuler.hs

main = putStrLn "Project Euler"

p1 :: Integral a => a -> a
p1 n = sum [x | x <- [1..n-1], mod x 3 == 0 || mod x 5 == 0]

p2 :: Integer -> Integer
p2 n = sum $ takeWhile (<=n) [x | x <- fibonacci, even x]

p3 :: Integral a => a -> a
p3 n = maximum $ primeFactorization n

p4 :: (Integral a, Integral b) => b -> a
p4 n = maximum [producted | a <-  [small..big], b <-  [a..big], let producted = a * b, isPalindromicNumber producted]
       where small = (10 ^ (n - 1))
             big = (small * 10) - 1

p5 :: Integral a => [a] -> a
p5 = leastCommonMultiple

p6 :: Integral a => [a] -> a
p6 [] = 0
p6 xs = ((sum xs) ^ 2) - (sum $ map (^2) xs)

p7 n = primeNumbers !! (n - 1)

p8 = p8' nums
    where p8' xs
              | length xs < 13 = 0
              | otherwise = max (product $ take 13 xs) (p8' $ tail xs)
          nums = sliceNum (read "73167176531330624919225119674426574742355349194934\
                                \96983520312774506326239578318016984801869478851843\
                                \85861560789112949495459501737958331952853208805511\
                                \12540698747158523863050715693290963295227443043557\
                                \66896648950445244523161731856403098711121722383113\
                                \62229893423380308135336276614282806444486645238749\
                                \30358907296290491560440772390713810515859307960866\
                                \70172427121883998797908792274921901699720888093776\
                                \65727333001053367881220235421809751254540594752243\
                                \52584907711670556013604839586446706324415722155397\
                                \53697817977846174064955149290862569321978468622482\
                                \83972241375657056057490261407972968652414535100474\
                                \82166370484403199890008895243450658541227588666881\
                                \16427171479924442928230863465674813919123162824586\
                                \17866458359124566529476545682848912883142607690042\
                                \24219022671055626321111109370544217506941658960408\
                                \07198403850962455444362981230987879927244284909188\
                                \84580156166097919133875499200524063689912560717606\
                                \05886116467109405077541002256983155200055935729725\
                                \71636269561882670428252483600823257530420752963450"::Integer)

p9 = p9' pythagorasNums
     where p9' [] = 0
           p9' ((a,b,c):xs) = if a + b + c == 1000
                              then a * b * c
                              else p9' xs

p10 n = sum $ takeWhile (<=n) primeNumbers

fibonacci :: [Integer]
fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

primeFactorization :: (Integral a) => a -> [a]
primeFactorization 0 = []
primeFactorization 1 = []
primeFactorization 2 = [2]
primeFactorization x = 
    let fstf = firstFactor x
        xx = div x fstf
    in [fstf] ++ primeFactorization xx

firstFactor :: Integral a => a -> a
firstFactor 0 = 0
firstFactor 1 = 1
firstFactor x = firstFactor' x 2
    where firstFactor' :: Integral a => a -> a -> a
          firstFactor' xx n
              | xx `mod` n == 0 = n
              | xx `div` 2 <= n = xx
              | otherwise = firstFactor' xx (n + 1)

                            
isPalindromicNumber :: Integral t => t -> Bool
isPalindromicNumber n = l == reverse l
    where l = sliceNum n

sliceNum :: Integral t => t -> [t]
sliceNum n
    | n < 10 = [n]
    | otherwise = sliceNum (div n 10) ++ [mod n 10]

leastCommonMultiple :: Integral a => [a] -> a
leastCommonMultiple [] = 0
leastCommonMultiple xs = product $ leastCommonMultiple' 0 xs
    where leastCommonMultiple' _ [] = []
          leastCommonMultiple' n (1:xxs) = leastCommonMultiple' n xxs
          leastCommonMultiple' n xxs
              | n <= 1 = let fstf = (firstFactor $ head xxs) in fstf:(leastCommonMultiple' fstf xxs)
              | otherwise = let divedList = div' xxs n in leastCommonMultiple' 1 divedList
          div' _ 0 = []
          div' xxs n
              | n == 1 = xxs
              | otherwise = map (\x -> let (d, m) = divMod x n in (if m == 0 then d else x)) xxs

-- http://notogawa.hatenablog.com/entry/20110114/1295006865
primeNumbers = p
    where p = 2:3:5#p;n#x@(m:p:y)=[n|gcd m n<2]++(n+2)#last(x:[m*p:y|p^2-3<n])

isPrimeNumber :: Integral a => a -> Bool
isPrimeNumber n
    | n <= 1 = False
    | otherwise = n == firstFactor n

pythagorasNums = [(a,b,c) | c <- [1..], b <- [1..c-1], a <- [1..b-1], a ^ 2 + b ^ 2 == c ^ 2]