A072106 The number of nontotients (even and odd) in the reduced residue system of n.

0, 0, 0, 1, 1, 1, 2, 3, 2, 3, 4, 3, 5, 5, 4, 7, 8, 5, 9, 7, 5, 9, 11, 7, 10, 11, 10, 11, 15, 7, 16, 15, 11, 15, 13, 11, 20, 17, 14, 15, 23, 11, 24, 19, 15, 21, 26, 15, 23, 19, 19, 23, 30, 17, 23, 23, 21, 27, 33, 15, 34, 29, 22, 31, 27, 19, 38, 31, 28, 23, 41, 23, 42, 35, 26, 35, 37

Offset: 1

Author

Labos Elemer, Jun 19 2002

Keywords

• nonn

Examples

			For n=113: the reduced residue system consists of 112 numbers: Card[OddNonTotients(113)] = 56 - 1, EvenNonTotients = {14,26,34,38,50,62,68,74,76,86,90,94,98}, i.e., 13 terms, therefore a(113) = 56 - 1 + 13 = 68.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A002202, A005277, A037225, A072451, A072455.

Programs

PARI

a(n) = sum(k = 1, n, gcd(n, k) == 1 && !istotient(k)); \\ Amiram Eldar, Nov 07 2024