[99p]Arith(Complete)

import List

-- problem 31
isPrime ::Integral a => a -> Bool
isPrime 1 = False
isPrime n = foldr (&&) True (map (0 /= ) (map (n `mod`) [2..n-1]))

-- problem 32
myGCD :: Integral a => a -> a -> a
myGCD 0 _ = 0
myGCD _ 0 = 0
myGCD m n
      | larger `mod` small == 0  = small
      | otherwise  = myGCD small (larger `mod` small)
      where larger = max m n
            small  = min m n

-- problem 33
coprime :: Integral a => a -> a -> Bool
coprime m n = (myGCD m n) ==1

-- problem 34
totient :: (Num b, Integral a) => a -> b
totient 0 = 0
totient 1 = 1
totient n = foldr (+) 0 (map f [1..n-1])
          where f x = if coprime x n then 1 else 0

-- problem 35
leastPrime :: Integral a => a -> a
leastPrime 1 = 1
leastPrime n = f n [2..n]
               where f n (x:xs) = if (n `mod` x == 0) then x else (f n xs)
primeFactor :: Integral a => a -> [a]
primeFactor 1 = []
primeFactor n = (leastPrime n) : primeFactor (n `div` (leastPrime n))

-- problem 36
encode :: Eq t => [t] -> [(t, Int)]
encode [] = []
encode xs = map (\x -> (head x,length x)) (group xs)
prime_factors_mult :: Integer -> [(Integer,Int)]
prime_factors_mult = encode . primeFactor

-- problem 37
totientK :: Integer -> Integer
totientK 0 = 0
totientK 1 = 1
totientK n = product [(p - 1) * p ^ (m - 1) | (p, m) <- prime_factors_mult n]

-- problem 39
primesR :: Integral t => t -> t -> [t]
primesR a b = [x | x <- [a..b], isPrime(x)]

-- problem 40
goldbach :: Integral t => t -> (t,t)
goldbach 0 = error "no answer"
goldbach 2 = error "no answer"
goldbach n
         | n `mod` 2 /=0  = error "not an even nat"
         | n `mod` 2 == 0  = head [(x,y) | x <- [2..(n `div` 2)],  y <- [(n `div` 2)..n], x+y == n, isPrime(x), isPrime(y)]

-- problem 41
goldbachList :: Integral t => t -> t -> [(t,t)]
goldbachList a b = [(goldbach x) | x <- [a..b], x>3, x `mod` 2 == 0]
goldbachList' :: Integral t => t -> t -> t -> [(t,t)]
goldbachList' a b k =[(goldbach x) | x <- [a..b], x>3, x `mod` 2 == 0, fst(goldbach x) >= k]