euler-totient-function.egi

-- 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, [2]), (3, 2, [3]), (4, 2, [2, 2]), (5, 4, [5]), (6, 2, [2, 3]),
   (7, 6, [7]), (8, 4, [2, 2, 2]), (9, 6, [3, 3]), (10, 4, [2, 5]),
   (11, 10, [11]), (12, 4, [2, 2, 3]), (13, 12, [13]), (14, 6, [2, 7]),
   (15, 8, [3, 5]), (16, 8, [2, 2, 2, 2]), (17, 16, [17]),
   (18, 6, [2, 3, 3]), (19, 18, [19]), (20, 8, [2, 2, 5])]