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
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).
A186974
Irregular triangle T(n,k), n>=1, 1<=k<=A036234(n), read by rows: T(n,k) is the number of k-element subsets of {1, 2, ..., n} having pairwise coprime elements.
Original entry on oeis.org
1, 2, 1, 3, 3, 1, 4, 5, 2, 5, 9, 7, 2, 6, 11, 8, 2, 7, 17, 19, 10, 2, 8, 21, 25, 14, 3, 9, 27, 37, 24, 6, 10, 31, 42, 26, 6, 11, 41, 73, 68, 32, 6, 12, 45, 79, 72, 33, 6, 13, 57, 124, 151, 105, 39, 6, 14, 63, 138, 167, 114, 41, 6, 15, 71, 159, 192, 128, 44, 6
Offset: 1
T(5,3) = 7 because there are 7 3-element subsets of {1,2,3,4,5} having pairwise coprime elements: {1,2,3}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}.
Irregular Triangle T(n,k) begins:
1;
2, 1;
3, 3, 1;
4, 5, 2;
5, 9, 7, 2;
6, 11, 8, 2;
7, 17, 19, 10, 2;
Rightmost terms of rows give
A319187.
-
with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i pi(n) +1:
b:= proc(t, n, k) option remember; local c, d, h;
if k=0 or k>n 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) +`if`(n<2, 0, T(n-1, 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_] := PrimePi[n]+1; 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] + If[n < 2, 0, t[n-1, k]]; Table[Table[t[n, k], { k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)
Showing 1-2 of 2 results.
Comments