Euler's Totient Function¶
Euler's totient $\varphi(n)$ counts integers in $\{1,\ldots,n\}$ that are coprime to $n$. If the distinct prime divisors of $n$ are $p_1,\ldots,p_k$, then
$$ \varphi(n) =n\prod_{j=1}^k\left(1-\frac1{p_j}\right). $$
The product formula makes prime factorization the natural computational route.
A direct typed definition¶
Prime factorization may contain repeated primes, so unique removes duplicates before the product is taken. Rational arithmetic keeps every intermediate factor exact even though the final result is an integer.
def φ (n : Integer) : Rational :=
n * product (map (\p -> 1 - 1 / p) (unique (pF n)))
Inspect one factorization¶
Since $36=2^2\,3^2$, only the distinct primes $2$ and $3$ enter:
$$ \varphi(36)=36(1-1/2)(1-1/3)=12. $$
(pF 36, unique (pF 36), φ 36)
The first twenty values¶
Displaying each $n$, its totient, and its complete prime factorization makes the jumps at primes and prime powers easy to compare.
map (\n -> (n, φ n, pF n)) (take 20 nats)
A divisor-sum identity¶
Every positive integer satisfies
$$ \sum_{d\mid n}\varphi(d)=n. $$
We can express the divisor condition with an ordinary filter and verify the identity on the same example.
def divisorsOf (n : Integer) : [Integer] :=
filter (\d -> divisor n d) [1..n]
def totientDivisorSum (n : Integer) : Rational :=
sum (map φ (divisorsOf n))
(divisorsOf 36, totientDivisorSum 36)
Takeaway¶
Euler's product formula becomes a one-line exact definition when factorization, uniqueness, mapping, and products compose directly. The divisor-sum check shows how the same function participates in a deeper arithmetic identity.