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.
