A164296 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 coprime to every other member of S(n).

1, 1, 2, 2, 2, 2, 2, 4, 3, 2, 2, 4, 3, 4, 3, 4, 3, 6, 4, 6, 5, 4, 4, 8, 5, 5, 4, 6, 4, 8, 5, 8, 6, 6, 5, 8, 5, 7, 5, 7, 5, 10, 6, 9, 7, 8, 6, 12, 7, 10, 7, 9, 7, 13, 8, 10, 8, 8, 7, 14, 8, 10, 8, 11, 8, 13, 8, 12, 9, 11, 9, 15, 10, 12, 10, 13, 10, 16, 10, 14, 11, 13, 10, 18, 11, 14, 10, 14, 10, 20

Offset

1,3

Comments

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

Links

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

Example

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 coprime to each other member -- these integers being 1, 5, and 7 -- then a(9) = 3.

Prog

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

Crossrefs

Cf. A164297.

Cf. A038566, A000010.

Sequence in context: A066691 A260123 A319411 * A319817 A233566 A319818

Adjacent sequences: A164293 A164294 A164295 * A164297 A164298 A164299

Keyword

nonn

Author

Leroy Quet, Aug 12 2009

Extensions

Extended by Ray Chandler, Mar 16 2010

Status

approved