

A015617


Number of (unordered) triples of integers from [1,n] with no common factors between pairs.


4



0, 0, 1, 2, 7, 8, 19, 25, 37, 42, 73, 79, 124, 138, 159, 183, 262, 277, 378, 405, 454, 491, 640, 668, 794, 850, 959, 1016, 1257, 1285, 1562, 1668, 1805, 1905, 2088, 2150, 2545, 2673, 2866, 2968, 3457, 3522, 4063, 4228, 4431, 4620, 5269, 5385, 5936
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Form the graph with nodes 1..n, joining two nodes by an edge if they are relatively prime; a(n) = number of triangles in this graph.  N. J. A. Sloane, Feb 06 2011. The number of edges in this graph is A015614.  Roberto Bosch Cabrera, Feb 07 2011.


LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..1000


FORMULA

For large n one can show that a(n) ~ C*binomial(n,3), where C = 0.28674... = A065473.  N. J. A. Sloane, Feb 06 2011.
a(n) = Sum_{r=1..n} Sum_{k=1..r} A186230(r,k).  Alois P. Heinz, Feb 17 2011


EXAMPLE

For n=5, there are a(5)=7 triples: (1,2,3), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,5) and (3,4,5) out of binomial(5,3) = 10 triples of distinct integers <= 5.


MATHEMATICA

a[n_] := Select[Subsets[Range[n], {3}], And @@ (GCD @@ # == 1 & /@ Subsets[#, {2}]) &] // Length; a /@ Range[49]
(* JeanFrançois Alcover, Jul 11 2011 *)


PROG

(PARI) a(n)=sum(a=1, n2, sum(b=a+1, n1, sum(c=b+1, n, gcd(a, b)==1 && gcd(a, c)==1 && gcd(b, c)==1))) \\ Charles R Greathouse IV, Apr 28 2015


CROSSREFS

Subset of A015616 (triples with no common factor) and A015631 (ordered triples with no common factor).
Cf. A185953 (first differences), A186230, Column 3 of triangle A186974.
Sequence in context: A287343 A101518 A055247 * A306903 A026579 A167767
Adjacent sequences: A015614 A015615 A015616 * A015618 A015619 A015620


KEYWORD

nonn


AUTHOR

Olivier Gérard


EXTENSIONS

Added one example and 2 crossreferences.  Olivier Gérard, Feb 06 2011.


STATUS

approved



