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

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

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:
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 *)

Crossrefs

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

Sequence in context: A372791 A062011 A375373 * A132857 A365264 A152782

Adjacent sequences: A225517 A225518 A225519 * A225521 A225522 A225523

Keyword

nonn

Author

R. J. Mathar, May 09 2013

Status

approved