login
A322389
Vertex-connectivity of the integer partition with Heinz number n.
19
0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 0, 2, 0, 1, 0, 2, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 0, 2
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.
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]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 05 2018
STATUS
approved