OFFSET
1,13
COMMENTS
The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
The vertex-connectivity of an integer partition is the minimum number of primes that must be divided out (and any parts then equal to 1 removed) so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.
LINKS
EXAMPLE
The integer partition (6,4,3) with Heinz number 455 does not become disconnected or empty if 2 is divided out giving (3,3), or if 3 is divided out giving (4,2), but it does become disconnected or empty if both 2 and 3 are divided out giving (); so a(455) = 2.
195 is the Heinz number of (6,3,2), corresponding to the multiset partition {{1},{2},{1,2}}. Removing the vertex 1 gives {{2},{2}}, while removing 2 gives {{1},{1}}. These are both connected, so both vertices must be removed to obtain a disconnected or empty multiset partition; hence a(195) = 2.
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
vertConn[y_]:=If[Length[csm[primeMS/@y]]!=1, 0, Min@@Length/@Select[Subsets[Union@@primeMS/@y], Function[del, Length[csm[DeleteCases[DeleteCases[primeMS/@y, Alternatives@@del, {2}], {}]]]!=1]]];
Array[vertConn@*primeMS, 100]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 05 2018
STATUS
approved