# 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 =
0

main =
Html.text
(if (test) then
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

1. Can you use the special fold `List.product`?

Solutions