A164297 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each non-coprime with at least one other member of S(n).

0, 0, 0, 0, 2, 0, 4, 0, 3, 2, 8, 0, 9, 2, 5, 4, 13, 0, 14, 2, 7, 6, 18, 0, 15, 7, 14, 6, 24, 0, 25, 8, 14, 10, 19, 4, 31, 11, 19, 9, 35, 2, 36, 11, 17, 14, 40, 4, 35, 10, 25, 15, 45, 5, 32, 14, 28, 20, 51, 2, 52, 20, 28, 21, 40, 7, 58, 20, 35, 13, 61, 9, 62, 24, 30, 23, 50, 8, 68, 18, 43, 27

Offset: 1

Author

Leroy Quet, Aug 12 2009

Keywords

• nonn

Comments

A164296(n) + A164297(n) = phi(n) (= A000010(n) = the number of elements in S(n)).

Examples

			The positive integers that are <= 9 and are coprime to 9 are: 1,2,4,5, 7,8. 1 is coprime to each other member in S(9). While 2, 4, and 8 are non-coprime to each other. 5 is coprime to each other member of S(9). And 7 is also coprime to each other member. Since there are 3 integers in S(9) that are each non-coprime with at least one other member of S(9) -- these integers being 2, 4, and 8 -- then a(9) = 3.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A164296, A036997, A048597.

Cf. A038566, A000010.

Programs

Haskell

import Data.List ((\\))
a164297 n = length [m | let ts = a038566_row n, m <- ts,
                        any ((> 1) . gcd m) (ts \\ [m])]
-- Reinhard Zumkeller, May 28 2015

Extensions

Extended by Ray Chandler, Mar 16 2010