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

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

Offset: 1

Author

R. J. Mathar, May 09 2013

Keywords

• nonn

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.

Examples

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

Links

• T. D. Noe, Table of n, a(n) for n = 1..359

Crossrefs

Cf. A076078 (subsets with lcm equal to n), A084422 (subsets of 1 through n).

Programs

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:
A225520 := proc(n)
    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 *)