login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A305193 Number of connected factorizations of n. 12
0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 5, 1, 1, 1, 4, 1, 1, 1, 2, 2, 1, 1, 7, 2, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 3, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 10, 1, 1, 2, 2, 1, 1, 1, 7, 5, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 2, 2, 5, 1, 1, 1, 4, 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 such that G(S) is a connected graph.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Nov 07 2018

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..20736

Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Index entries for sequences computed from exponents in factorization of n

EXAMPLE

The a(72) = 10 factorizations:

(72),

(2*2*18), (2*3*12), (2*6*6), (3*4*6),

(2*36), (3*24), (4*18), (6*12),

(2*2*3*6).

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]]}]];

Table[Length[Select[facs[n], Length[zsm[#]]==1&]], {n, 100}]

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)); };

A305193aux(n, m, facs) = if(1==n, is_connected(Set(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs, d); s += A305193aux(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Nov 07 2018

A305193(n) = if(1==n, 0, A305193aux(n, n, List([]))); \\ Antti Karttunen, Nov 07 2018

CROSSREFS

Cf. A048143, A281116, A286518, A286520, A290103, A303837, A304118, A304714, A304716, A305078, A305079, A319786.

Sequence in context: A327658 A319786 A321271 * A038538 A293515 A326622

Adjacent sequences:  A305190 A305191 A305192 * A305194 A305195 A305196

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 27 2018

EXTENSIONS

More terms from Antti Karttunen, Nov 07 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 05:25 EDT 2020. Contains 336290 sequences. (Running on oeis4.)