The totient function is defined for positive integers as:

\( \displaystyle \varphi(n) = \prod_{p | n} \left(1 - \frac{1}{p}\right)\)

where \( p \) is prime.

This leads to an algorithm for computing the totient function, which we can express thusly in Haskell:

import Control.Monad (join)

totient :: Int -> Int
totient n = foldr (\factor acc -> acc `div`

factor * (factor - 1)) n (uniquePrimeFactors n)

uniquePrimeFactors :: Int -> [Int]
uniquePrimeFactors = join go
where go 1 _ = []
go i n | n `rem` i == 0 && isPrime i = i : go (i-1) (reduce i n)
go i n = go (i-1) n
reduce i n | n `rem` i == 0 = reduce i (n `quot` i)
reduce _ n = n

isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = all ((/=0) . (x `rem`)) [2..up]
where up = floor (sqrt (fromIntegral x :: Double))

It is nontrivial to prove that this terminates;
this depends on the fact that a number has a unique prime factorization, and
that all prime numbers are greater than or equal to 2. None of this is
particularly advanced *mathematics*, but it makes a pretty strong case against the
current approach to termination checking used by Idris (for instance).

Moreover, this should be read as evidence that Turing was *morally* right, as know he
was *technically* right:
it is impossible to check if a program terminates in general, but most
of the functions where it is provably impossible to know when terminates are
pathological. This case demonstrates that merely finding a compiler algorithm that works on
common data strucutres (that is, integers) and functions is difficult.