Euler's Totient Function

Apr 19 2016
def φ $n := n * product (map (\$p -> 1 - 1 / p) (unique (pF n)))

take 100 (map2 2#(%1, %2, pF %2) 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]), (21, 12, [2, 2, 3]),
 (22, 10, [2, 5]), (23, 22, [2, 11]), (24, 8, [2, 2, 2]), (25, 20, [2, 2, 5]),
 (26, 12, [2, 2, 3]), (27, 18, [2, 3, 3]), (28, 12, [2, 2, 3]),
 (29, 28, [2, 2, 7]), (30, 8, [2, 2, 2]), (31, 30, [2, 3, 5]),
 (32, 16, [2, 2, 2, 2]), (33, 20, [2, 2, 5]), (34, 16, [2, 2, 2, 2]),
 (35, 24, [2, 2, 2, 3]), (36, 12, [2, 2, 3]), (37, 36, [2, 2, 3, 3]),
 (38, 18, [2, 3, 3]), (39, 24, [2, 2, 2, 3]), (40, 16, [2, 2, 2, 2]),
 (41, 40, [2, 2, 2, 5]), (42, 12, [2, 2, 3]), (43, 42, [2, 3, 7]),
 (44, 20, [2, 2, 5]), (45, 24, [2, 2, 2, 3]), (46, 22, [2, 11]),
 (47, 46, [2, 23]), (48, 16, [2, 2, 2, 2]), (49, 42, [2, 3, 7]),
 (50, 20, [2, 2, 5]), (51, 32, [2, 2, 2, 2, 2]), (52, 24, [2, 2, 2, 3]),
 (53, 52, [2, 2, 13]), (54, 18, [2, 3, 3]), (55, 40, [2, 2, 2, 5]),
 (56, 24, [2, 2, 2, 3]), (57, 36, [2, 2, 3, 3]), (58, 28, [2, 2, 7]),
 (59, 58, [2, 29]), (60, 16, [2, 2, 2, 2]), (61, 60, [2, 2, 3, 5]),
 (62, 30, [2, 3, 5]), (63, 36, [2, 2, 3, 3]), (64, 32, [2, 2, 2, 2, 2]),
 (65, 48, [2, 2, 2, 2, 3]), (66, 20, [2, 2, 5]), (67, 66, [2, 3, 11]),
 (68, 32, [2, 2, 2, 2, 2]), (69, 44, [2, 2, 11]), (70, 24, [2, 2, 2, 3]),
 (71, 70, [2, 5, 7]), (72, 24, [2, 2, 2, 3]), (73, 72, [2, 2, 2, 3, 3]),
 (74, 36, [2, 2, 3, 3]), (75, 40, [2, 2, 2, 5]), (76, 36, [2, 2, 3, 3]),
 (77, 60, [2, 2, 3, 5]), (78, 24, [2, 2, 2, 3]), (79, 78, [2, 3, 13]),
 (80, 32, [2, 2, 2, 2, 2]), (81, 54, [2, 3, 3, 3]), (82, 40, [2, 2, 2, 5]),
 (83, 82, [2, 41]), (84, 24, [2, 2, 2, 3]), (85, 64, [2, 2, 2, 2, 2, 2]),
 (86, 42, [2, 3, 7]), (87, 56, [2, 2, 2, 7]), (88, 40, [2, 2, 2, 5]),
 (89, 88, [2, 2, 2, 11]), (90, 24, [2, 2, 2, 3]), (91, 72, [2, 2, 2, 3, 3]),
 (92, 44, [2, 2, 11]), (93, 60, [2, 2, 3, 5]), (94, 46, [2, 23]),
 (95, 72, [2, 2, 2, 3, 3]), (96, 32, [2, 2, 2, 2, 2]),
 (97, 96, [2, 2, 2, 2, 2, 3]), (98, 42, [2, 3, 7]), (99, 60, [2, 2, 3, 5]),
 (100, 40, [2, 2, 2, 5])]
Links

Back to the Table of Contents