|
|
A225520
|
|
The number of subsets of the set of divisors of n in which elements are pairwise coprime.
|
|
11
|
|
|
2, 4, 4, 6, 4, 10, 4, 8, 6, 10, 4, 16, 4, 10, 10, 10, 4, 16, 4, 16, 10, 10, 4, 22, 6, 10, 8, 16, 4, 30, 4, 12, 10, 10, 10, 26, 4, 10, 10, 22, 4, 30, 4, 16, 16, 10, 4, 28, 6, 16, 10, 16, 4, 22, 10, 22, 10, 10, 4, 50, 4, 10, 16, 14, 10, 30, 4, 16, 10, 30, 4, 36
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Note that this is not 1+A048691(n); n=30 is a counterexample.
The number of all subsets of the set of divisors (without the restriction) is 2^A000005(n), which therefore is an upper bound of the current sequence.
|
|
LINKS
|
|
|
EXAMPLE
|
For n=6, the set of divisors is {1,2,3,6} and the a(6)=10 subsets with pairwise coprime entries are {}, {1}, {2}, {3}, {6}, {1,2}, {1,3}, {1,6}, {2,3} and {1,2,3}.
|
|
MAPLE
|
paircoprime := proc(s)
local L, i, j ;
L := convert(s, list) ;
for i from 1 to nops(L)-1 do
for j from i+1 to nops(L) do
if igcd(op(i, L), op(j, L)) <> 1 then
return false;
end if;
end do:
end do:
return true;
end proc:
local dvs, a, p ;
dvs := numtheory[divisors](n) ;
a := 0 ;
for p in combinat[powerset](dvs) do
if paircoprime(p) then
a := a+1 ;
end if;
end do:
a ;
end proc:
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Divisors[n]], If[Length[#] < 2, True, If[Length[#] == 2, CoprimeQ @@ #, And @@ CoprimeQ @@ #]]] &]], {n, 100}] (* T. D. Noe, May 09 2013 *)
|
|
CROSSREFS
|
Cf. A076078 (subsets with lcm equal to 1).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|