login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A015617 Number of (unordered) triples of integers from [1,n] with no common factors between pairs. 3
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]

(* 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: A213037 A101518 A055247 * A026579 A167767 A054601

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 25 21:19 EDT 2017. Contains 284111 sequences.