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,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]
(* Jean-François Alcover, Jul 11 2011 *)

Prog

(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

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 cross-references. - Olivier Gérard, Feb 06 2011.

Status

approved