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

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

Offset: 1

Author

Olivier Gérard

Keywords

• nonn

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.

Examples

			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.
		

Links

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

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.

Programs

Mathematica

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

PARI

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

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

Extensions

Added one example and 2 cross-references. - Olivier Gérard, Feb 06 2011.