cp's OEIS Frontend

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

%I A305566 #13 Jun 07 2018 22:01:23
%S A305566 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,
%T A305566 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,
%U A305566 1590,0,2,10,0,2,84,0,10,2,84,0,1156,0,2,10,10,2
%N A305566 Number of finite sets of relatively prime positive integers > 1 with least common multiple n.
%C A305566 From _Robert Israel_, Jun 06 2018: (Start)
%C A305566 a(n) depends only on the prime signature of n.
%C A305566 If n is in A000961, a(n)=0.
%C A305566 If n is in A006881, a(n)=2. (End)
%C A305566 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
%H A305566 Robert Israel, <a href="/A305566/b305566.txt">Table of n, a(n) for n = 1..10000</a>
%e A305566 The a(12) = 10 sets:
%e A305566 {3,4},
%e A305566 {2,3,4}, {2,3,12}, {3,4,6}, {3,4,12},
%e A305566 {2,3,4,6}, {2,3,4,12}, {2,3,6,12}, {3,4,6,12},
%e A305566 {2,3,4,6,12}.
%p A305566 f:= proc(n) g(sort(map(t -> t[2],ifactors(n)[2]))) end proc:
%p A305566 f(1):= 0:
%p A305566 g:= proc(L) option remember;
%p A305566   local nL, Cands, nC, Cons, i;
%p A305566   nL:= nops(L);
%p A305566   Cands:= [[]];
%p A305566   for i from 1 to nL do
%p A305566     Cands:= [seq(seq([op(s),t],t=0..L[i]),s=Cands)];
%p A305566   od:
%p A305566   Cands:= remove(t -> max(t)=0, Cands);
%p A305566   nC:= nops(Cands);
%p A305566   Cons:= [seq(select(t -> Cands[t][i]=0, {$1..nC}),i=1..nL),
%p A305566           seq(select(t -> Cands[t][i]=L[i], {$1..nC}), i=1..nL)];
%p A305566   h(Cons, {$1..nC})
%p A305566 end proc:
%p A305566 h:= proc(Cons, Cands)
%p A305566   local t,i,Consi, Candsi;
%p A305566   if Cons = [] then return 2^nops(Cands) fi;
%p A305566   t:= 0;
%p A305566   for i from 1 to nops(Cons[1]) do
%p A305566     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]);
%p A305566     if member({},Consi) then next fi;
%p A305566     Candsi:= Cands minus Cons[1][1..i];
%p A305566     t:= t + procname(Consi, Candsi)
%p A305566   od;
%p A305566   t
%p A305566 end proc:
%p A305566 map(f, [$1..100]); # _Robert Israel_, Jun 07 2018
%t A305566 Table[Length[Select[Subsets[Rest[Divisors[n]]],And[GCD@@#==1,LCM@@#==n]&]],{n,100}]
%Y A305566 Cf. A000961, A006881, A076078, A181819, A281116, A285572, A290103, A304818, A305563, A305564, A305565, A305567.
%K A305566 nonn
%O A305566 1,6
%A A305566 _Gus Wiseman_, Jun 05 2018