A286518 - OEIS

%I #35 Feb 19 2024 16:49:25

%S 1,1,1,2,1,4,1,4,2,4,1,20,1,4,4,8,1,20,1,20,4,4,1,88,2,4,4,20,1,96,1,

%T 16,4,4,4,196,1,4,4,88,1,96,1,20,20,4,1,368,2,20,4,20,1,88,4,88,4,4,1,

%U 1824,1,4,20,32,4,96,1,20,4,96,1,1688,1,4,20,20,4,96,1,368,8,4,1,1824,4,4,4,88,1,1824,4,20

%N Number of finite connected sets of positive integers greater than one with least common multiple n.

%C Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that are not relatively prime. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph.

%C a(n) depends only on prime signature of n (cf. A025487). - _Antti Karttunen_, Feb 17 2024

%H Antti Karttunen, <a href="/A286518/b286518.txt">Table of n, a(n) for n = 1..719</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%F From _Antti Karttunen_, Feb 17 2024: (Start)

%F a(n) <= A069626(n).

%F It seems that a(n) >= A318670(n), for all n > 1.

%F (End)

%e The a(6)=4 sets are: {6}, {2,6}, {3,6}, {2,3,6}.

%t zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];

%t Table[Length[Select[Subsets[Rest[Divisors[n]]],zsm[#]==={n}&]],{n,2,20}]

%o (PARI)

%o isconnected(facs) = { my(siz=length(facs)); if(1==siz,1,my(m=matrix(siz,siz,i,j,(gcd(facs[i],facs[j])!=1))^siz); for(n=1,siz,if(0==vecmin(m[n,]),return(0))); (1)); };

%o A286518aux(n, parts, from=1, ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==n && isconnected(ss), s++); for(i=from, k, newss = List(ss); listput(newss, parts[i]); s += A286518aux(n, parts, i+1, newss)); (s) };

%o A286518(n) = if(1==n, n, A286518aux(n, divisors(n))); \\ _Antti Karttunen_, Feb 17 2024

%Y Cf. A048143, A054921, A069626, A076078, A259936, A281116, A285572, A285573, A286520, A305193, A318670.

%K nonn

%O 1,4

%A _Gus Wiseman_, Jul 24 2017

%E Term a(1)=1 prepended and more terms added by _Antti Karttunen_, Feb 17 2024