A305079 - OEIS

%I #21 Dec 08 2018 21:01:33

%S 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,

%T 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,

%U 2,3,1,4,1,2,2,3,2,2,1,5,1,2,1,3,2,2,1

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

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

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

%C 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).

%H Antti Karttunen, <a href="/A305079/b305079.txt">Table of n, a(n) for n = 1..16384</a>

%H Antti Karttunen, <a href="/A305079/a305079.txt">Data supplement: n, a(n) computed for n =  1..100000</a>

%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>

%H <a href="/index/He#Heinz">Index entries for sequences related to Heinz numbers</a>

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

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

%F 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.

%F a(n) = A305501(A064989(n)) + A007814(n). - _Antti Karttunen_, Nov 10 2018

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

%t primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t 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]]]]]]]]];

%t Table[Length[zsm[primeMS[n]]],{n,100}]

%o (PARI)

%o 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); };

%o A007814(n) = valuation(n,2);

%o A000265(n) = (n/2^A007814(n));

%o 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

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

%K nonn

%O 1,4

%A _Gus Wiseman_, May 24 2018

%E Terms and Mathematica program corrected by _Gus Wiseman_, Nov 10 2018