Euler's Totient Function

-- Euler's totient function φ(n) def φ (n: Integer) : Rational := n * product (map (\$p -> 1 - 1 / p) (unique (pF n))) assertEqual "first 20 values of φ with factorization" (take 20 (map2 (\n1 n2 -> (n1, n2, pF n1)) nats (map φ nats))) [(1, 1, []), (2, 1, []), (3, 2, [2]), (4, 2, [2]), (5, 4, [2, 2]), (6, 2, [2]), (7, 6, [2, 3]), (8, 4, [2, 2]), (9, 6, [2, 3]), (10, 4, [2, 2]), (11, 10, [2, 5]), (12, 4, [2, 2]), (13, 12, [2, 2, 3]), (14, 6, [2, 3]), (15, 8, [2, 2, 2]), (16, 8, [2, 2, 2]), (17, 16, [2, 2, 2, 2]), (18, 6, [2, 3]), (19, 18, [2, 3, 3]), (20, 8, [2, 2, 2])]

Links

Back to the Table of Contents