A305079 Number of connected components of the integer partition with Heinz number n.

0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 3, 1, 5, 2, 2, 2, 3, 1, 2, 1, 4, 1, 2, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 2, 2, 4, 1, 2, 1, 4, 1, 2, 1, 6, 1, 3, 1, 3, 2, 3, 1, 4, 1, 2, 2, 3, 2, 2, 1, 5, 1, 2, 1, 3, 2, 2, 1

Offset

1,4

Comments

First differs from |A305052(n)| at a(169) = 1, A305052(169) = 0.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Given a finite multiset 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. If S is the integer partition with Heinz number n, a(n) is the number of connected components of G(S).

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Antti Karttunen, Data supplement: n, a(n) computed for n =  1..100000

Index entries for sequences computed from indices in prime factorization

Index entries for sequences related to Heinz numbers

Formula

For all n, k > 0, we have a(2^n * k) = n + a(k).

For all x, y > 0, we have a(x * y) <= a(x) + a(y).

For x, y > 0 strongly coprime, we have a(x * y) = a(x) + a(y). Strongly coprime means every prime index of x is coprime to every prime index of y, where a prime index of n is a number m such that prime(m) divides n.

a(n) = A305501(A064989(n)) + A007814(n). - Antti Karttunen, Nov 10 2018

Example

The a(315) = 2 connected components of {2,2,3,4} are {{3},{2,2,4}}.

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[Sort[Append[Delete[s, List/@c[[1]]], LCM@@s[[c[[1]]]]]]]]];
Table[Length[zsm[primeMS[n]]], {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); };
A007814(n) = valuation(n, 2);
A000265(n) = (n/2^A007814(n));
A305079(n) = if(!(n%2), A007814(n)+A305079(A000265(n)), my(cs = apply(p -> 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 10 2018

Crossrefs

Cf. A001221, A048143, A056239, A112798, A286518, A286520, A290103, A302242, A303837, A304118, A304714, A304716, A305052, A305055, A305078, A305501.

Sequence in context: A363522 A091090 A305052 * A319841 A336099 A290090

Adjacent sequences: A305076 A305077 A305078 * A305080 A305081 A305082

Keyword

nonn

Author

Gus Wiseman, May 24 2018

Extensions

Terms and Mathematica program corrected by Gus Wiseman, Nov 10 2018

Status

approved