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

%I #14 Feb 03 2018 12:10:29

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

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

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

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

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

%t A[n_] := Length[

%t ConnectedComponents[

%t AdjacencyGraph[Map[Boole[# != 1] &, Array[GCD, {n, n}], {2}]]]]

%t Table[A[n], {n, 1, 107}]

%o (PARI) a(n) = 1 + primepi(n) - primepi(n / 2) + (n >= 4); \\ _Michel Marcus_, Jan 09 2018

%Y Cf. A000720.

%K nonn

%O 1,2

%A _Luc Rousseau_, Jan 01 2018