cp's OEIS Frontend

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

%I A286518 #35 Feb 19 2024 16:49:25
%S A286518 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 A286518 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 A286518 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 A286518 Number of finite connected sets of positive integers greater than one with least common multiple n.
%C A286518 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 A286518 a(n) depends only on prime signature of n (cf. A025487). - _Antti Karttunen_, Feb 17 2024
%H A286518 Antti Karttunen, <a href="/A286518/b286518.txt">Table of n, a(n) for n = 1..719</a>
%H A286518 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A286518 From _Antti Karttunen_, Feb 17 2024: (Start)
%F A286518 a(n) <= A069626(n).
%F A286518 It seems that a(n) >= A318670(n), for all n > 1.
%F A286518 (End)
%e A286518 The a(6)=4 sets are: {6}, {2,6}, {3,6}, {2,3,6}.
%t A286518 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 A286518 Table[Length[Select[Subsets[Rest[Divisors[n]]],zsm[#]==={n}&]],{n,2,20}]
%o A286518 (PARI)
%o A286518 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 A286518 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 A286518(n) = if(1==n, n, A286518aux(n, divisors(n))); \\ _Antti Karttunen_, Feb 17 2024
%Y A286518 Cf. A048143, A054921, A069626, A076078, A259936, A281116, A285572, A285573, A286520, A305193, A318670.
%K A286518 nonn
%O A286518 1,4
%A A286518 _Gus Wiseman_, Jul 24 2017
%E A286518 Term a(1)=1 prepended and more terms added by _Antti Karttunen_, Feb 17 2024