A036997 Number of composite numbers <= n and relatively prime to n.

0, 0, 0, 0, 1, 0, 2, 0, 2, 1, 5, 0, 6, 1, 3, 2, 9, 0, 10, 1, 5, 3, 13, 0, 11, 4, 9, 4, 18, 0, 19, 5, 10, 6, 14, 2, 24, 7, 13, 5, 27, 1, 28, 7, 11, 9, 31, 2, 27, 6, 18, 10, 36, 3, 25, 9, 21, 13, 41, 1, 42, 13, 19, 14, 31, 4, 47, 14, 26, 7, 50, 5, 51, 16, 20, 16, 40, 5, 56, 11, 32, 19, 59, 3

Offset

1,7

Comments

30 is the largest number n with the property that if 1 < k < n and k is relatively prime to n, then k is prime. In other words, a(30) = 0 and if m > 30, then a(m) > 0. - Jonathan Sondow, Dec 08 2012

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Formula

A048864(n) = a(n) + 1. - Peter Luschny, Oct 22 2010

Mathematica

Table[ Count[ Select[ Range[ n ], GCD[ #, n ]===1& ], q_/; !(PrimeQ[ q ]||q===1) ], {n, 180} ]

Crossrefs

Cf. A048597 (indices where a(n) = 0), A048865 (number of primes p < n that are relatively prime to n).

Sequence in context: A242691 A081082 A049785 * A116900 A254372 A354158

Adjacent sequences: A036994 A036995 A036996 * A036998 A036999 A037000

Keyword

nonn

Author

Wouter Meeussen

Extensions

Minor edits by Ray Chandler, Mar 16 2010

Status

approved