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

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

2. Solutions

   Solutions