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

Author

Wouter Meeussen

Keywords

• nonn

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

Crossrefs

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

Programs

Mathematica

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

Formula

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

Extensions

Minor edits by Ray Chandler, Mar 16 2010