login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A186975
Irregular triangle T(n,k), n>=1, 1<=k<=A186971(n), read by rows: T(n,k) is the number of subsets of {1, 2, ..., n} containing n and having <=k pairwise coprime elements.
10
1, 1, 2, 1, 3, 4, 1, 3, 4, 1, 5, 10, 12, 1, 3, 4, 1, 7, 18, 26, 28, 1, 5, 11, 15, 16, 1, 7, 19, 29, 32, 1, 5, 10, 12, 1, 11, 42, 84, 110, 116, 1, 5, 11, 15, 16, 1, 13, 58, 137, 209, 242, 248, 1, 7, 21, 37, 46, 48, 1, 9, 30, 55, 69, 72, 1, 9, 33, 69, 98, 110, 112
OFFSET
1,3
COMMENTS
T(n,k) = T(n,k-1) for k>A186971(n). The triangle contains all values of T up to the last element of each row that is different from its predecessor.
LINKS
FORMULA
T(n,k) = Sum_{i=1..k} A186972(n,i).
EXAMPLE
T(5,3) = 10 because there are 10 subsets of {1,2,3,4,5} containing n and having <=3 pairwise coprime elements: {5}, {1,5}, {2,5}, {3,5}, {4,5}, {1,2,5}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}.
Triangle T(n,k) begins:
1;
1, 2;
1, 3, 4;
1, 3, 4;
1, 5, 10, 12;
1, 3, 4;
1, 7, 18, 26, 28;
MAPLE
with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i<r, i, 1), i=factorset(m)) end:
a:= proc(n) option remember; `if`(n<4, n, pi(n)-nops(factorset(n))+2) end:
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`(k=0, 0, T(n, k-1))
end:
seq(seq(T(n, k), k=1..a(n)), n=1..20);
MATHEMATICA
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]+If[k == 0, 0, t[n, k-1]]; Table[Table[t[n, k], {k, 1, a[n]}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)
CROSSREFS
Columns k=1-9 give: A000012, A039649 for n>1, A186987, A186988, A186989, A186990, A186991, A186992, A186993.
Rightmost elements of rows give A186973.
Sequence in context: A276237 A059663 A338367 * A027422 A135086 A210561
KEYWORD
nonn,look,tabf
AUTHOR
Alois P. Heinz, Mar 02 2011
STATUS
approved