A297616 a(n) is the number of connected components in the graph with vertices 1..n and adjacency criterion i and j not coprime.

1, 2, 3, 3, 4, 3, 4, 4, 4, 3, 4, 4, 5, 4, 4, 4, 5, 5, 6, 6, 6, 5, 6, 6, 6, 5, 5, 5, 6, 6, 7, 7, 7, 6, 6, 6, 7, 6, 6, 6, 7, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 8, 9, 9, 10, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 12, 11, 11, 11, 11, 11, 12, 12, 12, 11, 12, 12, 12, 11, 11, 11, 12, 12, 12, 12, 12, 11, 11, 11, 12

Offset

1,2

Links

Table of n, a(n) for n=1..97.

Formula

a(n) = 1 + pi(n) - pi(n / 2) + [n >= 4], where pi denotes the prime counting function (A000720, generalized to reals), and [] the Iverson bracket.

Mathematica

A[n_] := Length[
  ConnectedComponents[
   AdjacencyGraph[Map[Boole[# != 1] &, Array[GCD, {n, n}], {2}]]]]
Table[A[n], {n, 1, 107}]

Prog

(PARI) a(n) = 1 + primepi(n) - primepi(n / 2) + (n >= 4); \\ Michel Marcus, Jan 09 2018

Crossrefs

Cf. A000720.

Sequence in context: A285203 A085887 A305716 * A213251 A049108 A179846

Adjacent sequences: A297613 A297614 A297615 * A297617 A297618 A297619

Keyword

nonn

Author

Luc Rousseau, Jan 01 2018

Status

approved