I have this function which takes an integer n, and returns the number of integers less than n which are coprime with n. I don't know where my code might be failing as I think I check everything needed for it to work.
I expect an output like this:
eTotient 73 = 72
But I have one that looks like this:
eTotient 73 = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72]
Here is my code:
divisorCoPrime :: Int -> [Maybe Int]
divisorCoPrime n = divisorCoPrime2 n n
divisorCoPrime2 :: Int -> Int -> [Maybe Int]
divisorCoPrime2 n 1 = []
divisorCoPrime2 n x
| divides n x && isPrime x = Just x:divisorCoPrime2 n (x-1)
| otherwise = divisorCoPrime2 n (x-1)
isCoprime :: Int -> Int -> Bool
isCoprime x y = isCoprime2 (divisorCoPrime x) (divisorCoPrime y)
isCoprime2 :: [Maybe Int] -> [Maybe Int] -> Bool
isCoprime2 [] y = True
isCoprime2 x [] = True
isCoprime2 (x:xs) y
| foldl (||) False (map (x==) y) = False
| otherwise = isCoprime2 xs y
eTotient :: Int -> [Int]
eTotient n = filter (isCoprime n ) [2..(n-1)]
According to Wikipedia:
Euler's totient function [which is what I'm guessing
eTotient
is supposed to be] counts the positive integers up to a given integern
that are relatively prime ton
filter (isCoprime n ) [2..(n-1)]
is a list of such integers, but you want the number of these integers - the length of the list. Assuming the rest of the code is correct, that would look like this:
eTotient :: Int -> Int
eTotient n = length $ filter (isCoprime n ) [2..(n-1)]