オイラーのφ関数

Apr 19 2016

-- 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])]

リンク

Egison 数学ノート目次に戻る