login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A305253 Number of connected factorizations of n into factors greater than 1 whose distinct factors are pairwise indivisible. 4
0, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 2, 1 (list; graph; refs; listen; history; text; internal format)
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
a(n) <= A305193(n) <= A001055(n). - Antti Karttunen, Dec 06 2018
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
Sequence in context: A288636 A089723 A363741 * A294336 A316782 A326647
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 28 2018
EXTENSIONS
Definition clarified by Gus Wiseman, more terms from Antti Karttunen, Dec 06 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)