A305566 Number of finite sets of relatively prime positive integers > 1 with least common multiple n.

0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 10, 0, 2, 2, 0, 0, 10, 0, 10, 2, 2, 0, 44, 0, 2, 0, 10, 0, 84, 0, 0, 2, 2, 2, 122, 0, 2, 2, 44, 0, 84, 0, 10, 10, 2, 0, 184, 0, 10, 2, 10, 0, 44, 2, 44, 2, 2, 0, 1590, 0, 2, 10, 0, 2, 84, 0, 10, 2, 84, 0, 1156, 0, 2, 10, 10, 2

Offset

1,6

Comments

From Robert Israel, Jun 06 2018: (Start)

a(n) depends only on the prime signature of n.

If n is in A000961, a(n)=0.

If n is in A006881, a(n)=2. (End)

If n = p^k*q, where p and q are distinct primes and k >= 1, then a(n) = 3*4^(k-1)-2^(k-1). - Robert Israel, Jun 07 2018

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Example

The a(12) = 10 sets:
{3,4},
{2,3,4}, {2,3,12}, {3,4,6}, {3,4,12},
{2,3,4,6}, {2,3,4,12}, {2,3,6,12}, {3,4,6,12},
{2,3,4,6,12}.

Maple

f:= proc(n) g(sort(map(t -> t[2], ifactors(n)[2]))) end proc:
f(1):= 0:
g:= proc(L) option remember;
  local nL, Cands, nC, Cons, i;
  nL:= nops(L);
  Cands:= [[]];
  for i from 1 to nL do
    Cands:= [seq(seq([op(s), t], t=0..L[i]), s=Cands)];
  od:
  Cands:= remove(t -> max(t)=0, Cands);
  nC:= nops(Cands);
  Cons:= [seq(select(t -> Cands[t][i]=0, {$1..nC}), i=1..nL),
          seq(select(t -> Cands[t][i]=L[i], {$1..nC}), i=1..nL)];
  h(Cons, {$1..nC})
end proc:
h:= proc(Cons, Cands)
  local t, i, Consi, Candsi;
  if Cons = [] then return 2^nops(Cands) fi;
  t:= 0;
  for i from 1 to nops(Cons[1]) do
    Consi:= map(proc(t) if member(Cons[1][i], t) then NULL else t minus Cons[1][1..i-1] fi end proc, Cons[2..-1]);
    if member({}, Consi) then next fi;
    Candsi:= Cands minus Cons[1][1..i];
    t:= t + procname(Consi, Candsi)
  od;
  t
end proc:
map(f, [$1..100]); # Robert Israel, Jun 07 2018

Mathematica

Table[Length[Select[Subsets[Rest[Divisors[n]]], And[GCD@@#==1, LCM@@#==n]&]], {n, 100}]

Crossrefs

Cf. A000961, A006881, A076078, A181819, A281116, A285572, A290103, A304818, A305563, A305564, A305565, A305567.

Sequence in context: A333783 A088886 A317636 * A326813 A137347 A024941

Adjacent sequences: A305563 A305564 A305565 * A305567 A305568 A305569

Keyword

nonn

Author

Gus Wiseman, Jun 05 2018

Status

approved