1  ----------------------------------------------------------------------
   2  -- Project Euler: http://projecteuler.net/index.php?section=problems
   3  
   4  module Main where
   5  
   6  -- Helpers
   7  
   8  primeFactors 1 = []
   9  primeFactors x = first : primeFactors rest where
  10                    (first, rest) = splitPrimes x
  11                    splitPrimes n = (p, n `div` p) where p = tryDiv 2 n
  12                    tryDiv p n = case n `mod` p of
  13                                   0 -> p
  14                                   _ -> tryDiv (p + 1) n
  15  
  16  fibs = 1 : 2 : zipWith (+) fibs (tail fibs)
  17  
  18  primes = 2 : filter (isPrime primes) [3, 5..] where
  19             isPrime p n = all (/= 0) $ map (n `mod`) $ toTry p n
  20             toTry p n = takeWhile (<= (floor $ sqrt $ fromInteger n)) p
  21  
  22  chunk n l | (length l) < n = []
  23  chunk n l = take n l : chunk n (tail l)
  24  
  25  ----------------------------------------------------------------------
  26  -- ID 1:
  27  -- If we list all the natural numbers below 10 that are multiples of 3 or 5,
  28  -- we get 3, 5, 6 and 9. The sum of these multiples is 23.
  29  --
  30  -- Find the sum of all the multiples of 3 or 5 below 1000.
  31  
  32  id_1 = sum $ filter mod35 [1..999] where
  33           mod35 x = ((x `mod` 3) == 0) || ((x `mod` 5) == 0)
  34  
  35  ----------------------------------------------------------------------
  36  -- ID 2:
  37  -- Each new term in the Fibonacci sequence is generated by adding the previous
  38  -- two terms. By starting with 1 and 2, the first 10 terms will be:
  39  --
  40  --   1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  41  --
  42  -- Find the sum of all the even-valued terms in the sequence which do not exceed
  43  -- four million.
  44  
  45  id_2 = sum $ filter isEven $ takeWhile (< 4000000) fibs where
  46           isEven = ((== 0) . (`mod` 2))
  47  
  48  ----------------------------------------------------------------------
  49  -- ID 3:
  50  -- The prime factors of 13195 are 5, 7, 13 and 29.
  51  --
  52  -- What is the largest prime factor of the number 600851475143 ?
  53  
  54  id_3 = maximum $ primeFactors 600851475143
  55  
  56  ----------------------------------------------------------------------
  57  -- ID 4:
  58  -- A palindromic number reads the same both ways. The largest palindrome
  59  -- made from the product of two 2-digit numbers is 9009 = 91 x 99.
  60  --
  61  -- Find the largest palindrome made from the product of two 3-digit numbers.
  62  
  63  id_4 = maximum $ palindromes [100..999] [100..999] where
  64           palindromes xs ys = filter isPal [x * y | x <- xs, y <- ys]
  65           isPal n = (show n) == (reverse (show n))
  66  
  67  ----------------------------------------------------------------------
  68  -- ID 5:
  69  -- 2520 is the smallest number that can be divided by each of the numbers
  70  -- from 1 to 10 without any remainder.
  71  --
  72  -- What is the smallest number that is evenly divisible by all of the
  73  -- numbers from 1 to 20?
  74  
  75  id_5 = foldl1 lcm [1..20]
  76  
  77  ----------------------------------------------------------------------
  78  -- ID 6:
  79  -- The sum of the squares of the first ten natural numbers is,
  80  --
  81  --   1^2 + 2^2 + ... + 10^2 = 385
  82  --
  83  -- The square of the sum of the first ten natural numbers is,
  84  --
  85  --   (1 + 2 + ... + 10)^2 = 55^2 = 3025
  86  --
  87  -- Hence the difference between the sum of the squares of the first ten
  88  -- natural numbers and the square of the sum is 3025 - 385 = 2640.
  89  --
  90  -- Find the difference between the sum of the squares of the first one
  91  -- hundred natural numbers and the square of the sum.
  92  
  93  id_6 = (squareSums [1..100]) - (sumSquares [1..100]) where
  94           sumSquares = sum . map (^2)
  95           squareSums = (^2) . sum
  96  
  97  ----------------------------------------------------------------------
  98  -- ID 7:
  99  -- By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we
 100  -- can see that the 6th prime is 13.
 101  --
 102  -- What is the 10001st prime number?
 103  
 104  id_7 = nthPrime 10001 where nthPrime n = primes !! (n - 1)
 105  
 106  ----------------------------------------------------------------------
 107  -- ID 8:
 108  -- Find the greatest product of five consecutive digits in the 1000-digit number.
 109  
 110  id_8_num = "73167176531330624919225119674426574742355349194934" ++
 111             "96983520312774506326239578318016984801869478851843" ++
 112             "85861560789112949495459501737958331952853208805511" ++
 113             "12540698747158523863050715693290963295227443043557" ++
 114             "66896648950445244523161731856403098711121722383113" ++
 115             "62229893423380308135336276614282806444486645238749" ++
 116             "30358907296290491560440772390713810515859307960866" ++
 117             "70172427121883998797908792274921901699720888093776" ++
 118             "65727333001053367881220235421809751254540594752243" ++
 119             "52584907711670556013604839586446706324415722155397" ++
 120             "53697817977846174064955149290862569321978468622482" ++
 121             "83972241375657056057490261407972968652414535100474" ++
 122             "82166370484403199890008895243450658541227588666881" ++
 123             "16427171479924442928230863465674813919123162824586" ++
 124             "17866458359124566529476545682848912883142607690042" ++
 125             "24219022671055626321111109370544217506941658960408" ++
 126             "07198403850962455444362981230987879927244284909188" ++
 127             "84580156166097919133875499200524063689912560717606" ++
 128             "05886116467109405077541002256983155200055935729725" ++
 129             "71636269561882670428252483600823257530420752963450"
 130  
 131  id_8 = maximum $ map (product . map read . explode) $ chunk 5 id_8_num where
 132           explode [] = []
 133           explode (h:t) = [h] : explode t
 134  
 135  ----------------------------------------------------------------------
 136  -- ID 9:
 137  -- A Pythagorean triplet is a set of three natural numbers, abc,
 138  -- for which,
 139  --
 140  --   a^2 + b^2 = c^2
 141  --
 142  -- For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
 143  --
 144  -- There exists exactly one Pythagorean triplet for which
 145  -- a + b + c = 1000. Find the product abc.
 146  
 147  id_9 = product $ head $ triplets
 148  triplets = [[a, b, c] | a <- [1..1000],
 149                          b <- [1..(1000-a)],
 150                          c <- [1000 - a - b],
 151                          a < b,
 152                          (a * a) + (b * b) == (c * c)]
 153  
 154  ----------------------------------------------------------------------
 155  -- ID 10:
 156  -- The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
 157  --
 158  -- Find the sum of all the primes below two million.
 159  
 160  id_10 = sum $ takeWhile (< 2000000) primes