A164297 - OEIS

%I #10 May 28 2015 04:08:09

%S 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,

%T 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,

%U 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

%N 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).

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

%H Reinhard Zumkeller, <a href="/A164297/b164297.txt">Table of n, a(n) for n = 1..1000</a>

%e 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.

%o (Haskell)

%o import Data.List ((\\))

%o a164297 n = length [m | let ts = a038566_row n, m <- ts,

%o                         any ((> 1) . gcd m) (ts \\ [m])]

%o -- _Reinhard Zumkeller_, May 28 2015

%Y Cf. A164296, A036997, A048597.

%Y  Cf. A038566, A000010.

%K nonn

%O 1,5

%A _Leroy Quet_, Aug 12 2009

%E Extended by _Ray Chandler_, Mar 16 2010