cp's OEIS Frontend

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

%I A225520 #19 Jun 13 2025 07:42:32
%S A225520 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 A225520 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 A225520 22,10,22,10,10,4,50,4,10,16,14,10,30,4,16,10,30,4,36
%N A225520 The number of subsets of the set of divisors of n in which elements are pairwise coprime.
%C A225520 Note that this is not 1+A048691(n); n=30 is a counterexample.
%C A225520 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 A225520 T. D. Noe, <a href="/A225520/b225520.txt">Table of n, a(n) for n = 1..359</a>
%e A225520 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 A225520 paircoprime := proc(s)
%p A225520     local L,i,j ;
%p A225520     L := convert(s,list) ;
%p A225520     for i from 1 to nops(L)-1 do
%p A225520         for j from i+1 to nops(L) do
%p A225520             if igcd(op(i,L),op(j,L)) <> 1 then
%p A225520                 return false;
%p A225520             end if;
%p A225520         end do:
%p A225520     end do:
%p A225520     return true;
%p A225520 end proc:
%p A225520 A225520 := proc(n)
%p A225520     local dvs,a,p ;
%p A225520     dvs := numtheory[divisors](n) ;
%p A225520     a := 0 ;
%p A225520     for p in combinat[powerset](dvs) do
%p A225520         if paircoprime(p) then
%p A225520             a := a+1 ;
%p A225520         end if;
%p A225520     end do:
%p A225520     a ;
%p A225520 end proc:
%t A225520 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 A225520 Cf. A076078 (subsets with lcm equal to n), A084422 (subsets of 1 through n).
%K A225520 nonn
%O A225520 1,1
%A A225520 _R. J. Mathar_, May 09 2013