|
%I #49 Oct 04 2018 18:44:14
%S 0,0,1,2,7,8,19,25,37,42,73,79,124,138,159,183,262,277,378,405,454,
%T 491,640,668,794,850,959,1016,1257,1285,1562,1668,1805,1905,2088,2150,
%U 2545,2673,2866,2968,3457,3522,4063,4228,4431,4620,5269,5385,5936
%N Number of (unordered) triples of integers from [1,n] with no common factors between pairs.
%C 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.
%H Charles R Greathouse IV, <a href="/A015617/b015617.txt">Table of n, a(n) for n = 1..1000</a>
%F 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.
%F a(n) = Sum_{r=1..n} Sum_{k=1..r} A186230(r,k). - _Alois P. Heinz_, Feb 17 2011
%e 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.
%t a[n_] := Select[Subsets[Range[n], {3}], And @@ (GCD @@ # == 1 & /@ Subsets[#, {2}]) &] // Length; a /@ Range[49]
%t (* _Jean-François Alcover_, Jul 11 2011 *)
%o (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
%Y Subset of A015616 (triples with no common factor) and A015631 (ordered triples with no common factor).
%Y Cf. A185953 (first differences), A186230, Column 3 of triangle A186974.
%K nonn
%O 1,4
%A _Olivier Gérard_
%E Added one example and 2 cross-references. - _Olivier Gérard_, Feb 06 2011.
|
