login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A305254 Number of factorizations f of n into factors greater than 1 such that the graph of f is a forest. 0
1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 5, 1, 7, 2, 2, 2, 8, 1, 2, 2, 7, 1, 5, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 11, 1, 2, 4, 11, 2, 5, 1, 4, 2, 5, 1, 14, 1, 2, 4, 4, 2, 5, 1, 12, 5, 2, 1, 11, 2 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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 with a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. This sequence counts factorizations f such that G(U(f)) is a forest, meaning it has no cycles, where U(f) is the set of distinct elements of f.

LINKS

Table of n, a(n) for n=1..85.

EXAMPLE

The a(72) = 14 factorizations:

     (72)

    (2*36)     (3*24)    (4*18)    (8*9)

   (2*2*18)   (2*3*12)   (2*4*9)  (3*3*8) (3*4*6)

   (2*2*2*9)  (2*2*3*6) (2*3*3*4)

  (2*2*2*3*3)

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

zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];

Table[Length[Select[facs[n], Function[f, And@@(zensity[Select[f, Function[x, Divisible[#, x]]]]==-1&/@zsm[f])]]], {n, 200}]

CROSSREFS

Cf. A001970, A048143, A281116, A285572, A286518, A286520, A303386, A304714, A304716, A305149, A305193, A305253.

Sequence in context: A317791 A318559 A218320 * A252665 A001055 A320266

Adjacent sequences:  A305251 A305252 A305253 * A305255 A305256 A305257

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 28 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 March 20 21:49 EDT 2019. Contains 321352 sequences. (Running on oeis4.)