|
%I #22 Mar 22 2024 16:52:57
%S 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,
%T 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,
%U 4,2,5,1,14,1,2,4,4,2,5,1,12,5,2,1,11,2
%N Number of factorizations f of n into factors greater than 1 such that the graph of f is a forest.
%C Given a factorization f consisting of positive integers greater than one, let G(F) be a multigraph with one vertex for each factor and n edges between any two vertices with n common divisors greater than 1. For example, G(6,14,15,35) is a 4-cycle; G(6,12) is a 2-cycle because 6 and 12 have multiple common divisors. This sequence counts factorizations f such that G(f) is a forest, meaning it has no cycles. [Comment edited by _Robert Munafo_, Mar 24 2024]
%e The a(72) = 14 factorizations:
%e (72)
%e (2*36) (3*24) (4*18) (8*9)
%e (2*2*18) (2*3*12) (2*4*9) (3*3*8) (3*4*6)
%e (2*2*2*9) (2*2*3*6) (2*3*3*4)
%e (2*2*2*3*3)
%e not counted: (2*6*6) because 6 and 6 share multiple divisors; likewise (6*12) because 6 and 12 share multiple divisors.
%t 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 zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
%t Table[Length[Select[facs[n],Function[f,And@@(zensity[Select[f,Function[x,Divisible[#,x]]]]==-1&/@zsm[f])]]],{n,200}]
%Y Cf. A001970, A048143, A281116, A285572, A286518, A286520, A303386, A304714, A304716, A305149, A305193, A305253.
%K nonn
%O 1,4
%A _Gus Wiseman_, May 28 2018
%E Extensive clarification by _Robert Munafo_, Mar 22 2024
|
