A185953 -id:A185953 - cp's OEIS frontend

A186972 Irregular triangle T(n,k), n>=1, 1<=k<=A186971(n), read by rows: T(n,k) is the number of k-element subsets of {1, 2, ..., n} containing n and having pairwise coprime elements.

1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 4, 5, 2, 1, 2, 1, 1, 6, 11, 8, 2, 1, 4, 6, 4, 1, 1, 6, 12, 10, 3, 1, 4, 5, 2, 1, 10, 31, 42, 26, 6, 1, 4, 6, 4, 1, 1, 12, 45, 79, 72, 33, 6, 1, 6, 14, 16, 9, 2, 1, 8, 21, 25, 14, 3, 1, 8, 24, 36, 29, 12, 2, 1, 16, 79, 183, 228, 157, 56, 8, 1, 6, 15, 20, 15, 6, 1

Offset: 1

Alois P. Heinz, Mar 01 2011

T(n,k) = 0 for k>A186971(n). The triangle contains all positive values of T.

			T(5,3) = 5 because there are 5 3-element subsets of {1,2,3,4,5} containing 5 and having pairwise coprime elements: {1,2,5}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}.
Irregular Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2,  1;
  1, 2,  1;
  1, 4,  5, 2;
  1, 2,  1;
  1, 6, 11, 8, 2;

Alois P. Heinz, Rows n = 1..220, flattened

Columns k=1-10 give: A000012, A000010 (for n>1), A185953, A185348, A186976, A186977, A186978, A186979, A186980, A186981.
Rightmost elements of rows give A186994.
Row sums are A186973.
Cf. A186971.

with(numtheory):
s:= proc(m,r) option remember; mul(`if`(in then 0
    elif k=1 then 1
    elif k=2 and t=n then `if`(n<2, 0, phi(n))
    else c:= 0;
         d:= 2-irem(t,2);
         for h from 1 to n-1 by d do
           if igcd(t, h)=1 then c:= c +b(s(t*h, h), h, k-1) fi
         od; c
      fi
end:
T:= proc(n,k) option remember; b(s(n,n),n,k) end:
seq(seq(T(n, k), k=1..a(n)), n=1..20);

s[m_, r_] := s[m, r] = Product[If[i < r, i, 1], {i, FactorInteger[m][[All, 1]]}]; a[n_] := a[n] = If[n < 4, n, PrimePi[n] - Length[FactorInteger[n]]+2]; b[t_, n_, k_] := b[t, n, k] = Module[{c, d, h}, Which[k == 0 || k > n, 0, k == 1, 1, k == 2 && t == n, If[n < 2, 0, EulerPhi[n]], True, c = 0; d = 2-Mod[t, 2]; For[h = 1, h <= n-1, h = h+d, If[GCD[t, h] == 1, c = c+b[s[t*h, h], h, k-1]]]; c]]; t[n_, k_] := t[n, k] = b[s[n, n], n, k]; Table[Table[t[n, k], {k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

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

Original entry on oeis.org

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

Olivier Gérard

nonn

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.

			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.

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

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.

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

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

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

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

A185348 Number of ordered quadruples of distinct pairwise coprime positive integers with largest element n; also first differences of A015623.

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 8, 4, 10, 2, 42, 4, 79, 16, 25, 36, 183, 20, 277, 50, 100, 70, 491, 56, 399, 139, 340, 146, 1016, 56, 1285, 398, 493, 342, 706, 184, 2150, 501, 807, 363, 2968, 210, 3522, 775, 935, 904, 4620, 508, 3732, 842, 2011, 1255, 6684, 728, 3355, 1304, 2785, 1877, 9141, 546

Offset: 1

Alois P. Heinz, Feb 15 2011

nonn

			a(4) = 0 because there is only one ordered quadruple of distinct positive integers with largest element 4, (1,2,3,4), but the elements are not pairwise coprime, 2 and 4 have a common factor >1.
a(8) = 4 because there are only four ordered quadruples of distinct pairwise coprime positive integers with largest element 8: (1,3,5,8), (1,3,7,8), (1,5,7,8), (3,5,7,8).

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A015623, A185953. Column 4 of triangle A186972.

A186987 Number of subsets of {1, 2, ..., n} containing n and having <=3 pairwise coprime elements.

Original entry on oeis.org

1, 2, 4, 4, 10, 4, 18, 11, 19, 10, 42, 11, 58, 21, 30, 33, 96, 22, 120, 36, 62, 48, 172, 37, 147, 69, 128, 70, 270, 37, 308, 123, 158, 117, 208, 75, 432, 147, 218, 119, 530, 78, 584, 186, 228, 212, 696, 133, 594, 191, 380, 256, 882, 166, 547

Offset: 1

Alois P. Heinz, Mar 03 2011

			a(6) = 4 because there are 4 subsets of {1,2,3,4,5,6} containing 6 and having <=3 pairwise coprime elements: {6}, {1,6}, {5,6}, {1,5,6}.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Column 3 of triangle A186975. Sum of A039649 and A185953 for n>1.

A186230 Triangle T(n,k), n>=1, 1<=k<=n, read by rows: T(n,k) is the number of positive integers j

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 2, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 2, 4, 2, 0, 0, 0, 1, 0, 2, 0, 3, 0, 0, 1, 0, 1, 3, 0, 4, 3, 0, 0, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 1, 2, 2, 4, 2, 6, 4, 6, 4, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 0, 0, 0, 1, 0, 2, 0, 0, 0, 2, 0, 4, 0, 5, 0

Offset: 1

Alois P. Heinz, Feb 15 2011

T(n,k) = A000010(k) if n is prime and 1

			T(n,1) = 0 because no positive integer j<1 can be found.
T(n,k) = 0 if GCD(n,k)>1.
T(7,5) = 4 because for j in {1,2,3,4} all conditions are satisfied.
Triangle T(n,k) begins:
  0;
  0, 0;
  0, 1, 0;
  0, 0, 1, 0;
  0, 1, 2, 2, 0;
  0, 0, 0, 0, 1, 0;
  0, 1, 2, 2, 4, 2, 0;

Alois P. Heinz, Rows n = 1..250, flattened

Row sums give: A185953. Column k=2 gives: A000035 for n>1. Lower diagonal gives: A057475(n-1) for n>2. Cf. A000010, A000040, A003989.

with(numtheory):
T:= proc(n,k) local c, i, j, m;
      if k=1 or igcd(n, k)>1 then 0
    elif isprime(n) then phi(k)
    else m:= n*k;
         i:= igcd(m, 2);
         c:= 0;
         for j to k-1 by i do
           if igcd(m, j)=1 then c:= c+1 fi
         od; c
      fi
    end:
seq(seq(T(n, k), k=1..n), n=1..20);

t[n_, k_] := Module[{c, i, j, m}, If[ k == 1 || GCD[n, k] > 1, 0, If[PrimeQ[n], EulerPhi[k], m = n*k; i = GCD[m, 2]; c = 0; For[j = 1, j <= k-1, j = j+i, If[GCD[m, j] == 1, c = c+1]]; c]]]; Table[Table[t[n, k], {k, 1, n}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 19 2013 *)

T(n,k) = |{ j : 1 <= j < k and GCD(n,k) = GCD(n,j) = GCD(k,j) = 1 }|.

Showing 1-5 of 5 results.

cp's OEIS Frontend

A186972 Irregular triangle T(n,k), n>=1, 1<=k<=A186971(n), read by rows: T(n,k) is the number of k-element subsets of {1, 2, ..., n} containing n and having pairwise coprime elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A185348 Number of ordered quadruples of distinct pairwise coprime positive integers with largest element n; also first differences of A015623.

Views

Author

Keywords

Examples

Links

Crossrefs

A186987 Number of subsets of {1, 2, ..., n} containing n and having <=3 pairwise coprime elements.

Views

Author

Keywords

Examples

Links

Crossrefs

A186230 Triangle T(n,k), n>=1, 1<=k<=n, read by rows: T(n,k) is the number of positive integers j

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula