gistfile1.hs

import Data.List (nub, group)

-- problem 31
isPrime :: Int -> Bool
isPrime n = length (filter (\x -> (mod n x) == 0) [2..n-1]) == 0 && n > 1

-- problem 32
pgcd :: Int ->  Int -> Int
pgcd a 0 = a
pgcd a b = pgcd b (mod a b)


-- problem 33
coprime :: Int -> Int -> Bool
coprime a b = pgcd a b == 1

-- problem 34
totientPhi :: Int -> Int
totientPhi n = length $ filter (\x -> x == True) $ map (\x -> coprime n x) [1..n]

primes n = [x | x <- [2..n-1], isPrime x]

-- problem 35
primeFactor :: Int -> [Int]
primeFactor n =  reverse $ helper n (reverse $ primes n) [] 
                           where helper 1 _ acc = acc
                                 helper n [] acc = acc
                                 helper n (x:xs) acc = if mod n x == 0 then helper (div n x) xs (acc ++ [x]) else helper n xs acc


generatePrimeFactor :: Int -> [Int] -> [Int] -> [Int]
generatePrimeFactor 1 _ acc = acc
generatePrimeFactor n [] acc = acc
generatePrimeFactor n p@(x:xs) acc = if mod n x == 0 then generatePrimeFactor (div n x) p (acc ++ [x]) else generatePrimeFactor n xs acc

primeFactorAsc :: Int -> [Int]
primeFactorAsc n =  nub $ generatePrimeFactor n (primes n) [] 

-- problem 36 

primeFactorAsc' :: Int -> [(Int, Int)]
primeFactorAsc' n =  map (\x -> (head x, length x)) $ group $ generatePrimeFactor n (primes n) []

-- problem 37
phi :: Int -> Int
phi n = foldl (\acc x -> acc * ((fst x) - 1) * (fst x) ^ ((snd x) - 1))  1 (primeFactorAsc' n)

-- problem 39
primesR :: Int -> Int -> [Int]
primesR l u = [x | x <- [l..u-1], isPrime x]

-- problem 40
goldbach :: Int -> [(Int, Int)]
goldbach n = helper (primes n) n
            where helper [] n = []
                  helper (x:xs) n = [(x,v2) | v2 <- xs, x + v2 == n] ++ helper xs n 

oneGoldbach = head . goldbach

goldbachList :: Int -> Int -> [(Int, [(Int,Int)])]
goldbachList lower upper = map (\x -> (x, goldbach x)) [x | x <- [lower..upper], mod x 2 == 0]