Problem 37
Calculate Euler's totient function phi(m) (improved).
See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m
is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows:
Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime
factors and their multiplicities) of a given number m.
Then phi(m) can be calculated with the following formula:
phi(m) = ((p1 - 1) * p1 ^ (m1 - 1)) *
((p2 - 1) * p2 ^ (m2 - 1)) *
((p3 - 1) * p3 ^ (m3 - 1)) * ...
Unit Test
import Html
import List
phi : Int -> Int
phi n =
-- your implementation here
0
main =
Html.text
(if (test) then
"Your implementation passed all tests."
else
"Your implementation failed at least one test."
)
test : Bool
test =
List.all (\( result, expect ) -> result == expect)
[ ( phi 36, totient 36 )
, ( phi 10, totient 10 )
, ( phi 1, totient 1 )
, ( phi 0, totient 0 )
, ( phi 120, totient 120 )
, ( phi 2, totient 2 )
, ( phi 23, totient 23 )
, ( phi 69145, totient 69145 )
, ( phi 9007, totient 9007 )
, ( phi 36028, totient 36028 )
, ( phi 26028, totient 26028 )
]
totient : Int -> Int
totient n =
List.length <| coprimes n
coprimes : Int -> List Int
coprimes n =
List.filter (\x -> coprime n x) (List.range 1 n)
coprime : Int -> Int -> Bool
coprime a b =
gcd a b == 1
gcd : Int -> Int -> Int
gcd a b =
if b == 0 then
abs a
else
gcd b (a % b)
Hints
- Can you use the special fold
List.product
? Solutions