login
The number of subsets of the set of divisors of n in which elements are pairwise coprime.
11

%I #14 Feb 27 2020 20:14:06

%S 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,

%T 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,

%U 22,10,22,10,10,4,50,4,10,16,14,10,30,4,16,10,30,4,36

%N The number of subsets of the set of divisors of n in which elements are pairwise coprime.

%C Note that this is not 1+A048691(n); n=30 is a counterexample.

%C 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.

%H T. D. Noe, <a href="/A225520/b225520.txt">Table of n, a(n) for n = 1..359</a>

%e 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}.

%p paircoprime := proc(s)

%p local L,i,j ;

%p L := convert(s,list) ;

%p for i from 1 to nops(L)-1 do

%p for j from i+1 to nops(L) do

%p if igcd(op(i,L),op(j,L)) <> 1 then

%p return false;

%p end if;

%p end do:

%p end do:

%p return true;

%p end proc:

%p A225520 := proc(n)

%p local dvs,a,p ;

%p dvs := numtheory[divisors](n) ;

%p a := 0 ;

%p for p in combinat[powerset](dvs) do

%p if paircoprime(p) then

%p a := a+1 ;

%p end if;

%p end do:

%p a ;

%p end proc:

%t Table[Length[Select[Subsets[Divisors[n]], If[Length[#] < 2, True, If[Length[#] == 2, CoprimeQ @@ #, And @@ CoprimeQ @@ #]]] &]], {n, 100}] (* _T. D. Noe_, May 09 2013 *)

%Y Cf. A076078 (subsets with lcm equal to 1).

%K nonn

%O 1,1

%A _R. J. Mathar_, May 09 2013