OFFSET
1,4
COMMENTS
Given a finite multiset 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 with a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. This sequence counts factorizations S whose distinct factors are pairwise indivisible and such that G(S) is a connected graph.
LINKS
FORMULA
EXAMPLE
The a(360) = 8 factorizations: (360), (4*90), (10*36), (12*30), (15*24), (18*20), (4*6*15), (6*6*10).
MATHEMATICA
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]]]]]]]]];
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
sacs[n_]:=Select[facs[n], Function[f, Length[zsm[f]]==1&&Select[Tuples[Union[f], 2], UnsameQ@@#&&Divisible@@#&]=={}]]
Table[Length[sacs[n]], {n, 500}]
PROG
(PARI)
is_connected(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)); };
A305253aux(n, m, facs) = if(1==n, is_connected(Vec(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&factorback(apply(x -> (x==d)||(x%d), Vec(facs))), newfacs = List(facs); listput(newfacs, d); s += A305253aux(n/d, d, newfacs))); (s));
A305253(n) = if(1==n, 0, A305253aux(n, n, List([]))); \\ Antti Karttunen, Dec 06 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 28 2018
EXTENSIONS
Definition clarified by Gus Wiseman, more terms from Antti Karttunen, Dec 06 2018
STATUS
approved