login
A305501
Number of connected components of the integer partition y + 1 where y is the integer partition with Heinz number n.
3
0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 3, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 3
OFFSET
1,6
COMMENTS
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).
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. A partition y is said to be connected if G(U(y + 1)) is a connected graph, where U(y + 1) is the set of distinct successors of the parts of y.
This is intended to be a cleaner form of A305079, where the treatment of empty multisets is arbitrary.
EXAMPLE
The "prime index plus 1" multiset of 7410 is {2,3,4,7,9}, with connected components {{2,4},{3,9},{7}}, so a(7410) = 3.
MATHEMATICA
primeMS[n_]:=If[n===1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
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]]]]]]]]];
Table[Length[zsm[primeMS[n]+1]], {n, 100}]
PROG
(PARI)
zero_first_elem_and_connected_elems(ys) = { my(cs = List([ys[1]]), i=1); ys[1] = 0; while(i<=#cs, for(j=2, #ys, if(ys[j]&&(1!=gcd(cs[i], ys[j])), listput(cs, ys[j]); ys[j] = 0)); i++); (ys); };
A305501(n) = { my(cs = apply(p -> 1+primepi(p), factor(n)[, 1]~), s=0); while(#cs, cs = select(c -> c, zero_first_elem_and_connected_elems(cs)); s++); (s); }; \\ Antti Karttunen, Nov 09 2018
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 03 2018
EXTENSIONS
More terms from Antti Karttunen, Nov 09 2018
STATUS
approved