cp's OEIS Frontend

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

%I A305079 #21 Dec 08 2018 21:01:33
%S A305079 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 A305079 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 A305079 2,3,1,4,1,2,2,3,2,2,1,5,1,2,1,3,2,2,1
%N A305079 Number of connected components of the integer partition with Heinz number n.
%C A305079 First differs from |A305052(n)| at a(169) = 1, A305052(169) = 0.
%C A305079 The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).
%C A305079 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 A305079 Antti Karttunen, <a href="/A305079/b305079.txt">Table of n, a(n) for n = 1..16384</a>
%H A305079 Antti Karttunen, <a href="/A305079/a305079.txt">Data supplement: n, a(n) computed for n =  1..100000</a>
%H A305079 <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%H A305079 <a href="/index/He#Heinz">Index entries for sequences related to Heinz numbers</a>
%F A305079 For all n, k > 0, we have a(2^n * k) = n + a(k).
%F A305079 For all x, y > 0, we have a(x * y) <= a(x) + a(y).
%F A305079 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 A305079 a(n) = A305501(A064989(n)) + A007814(n). - _Antti Karttunen_, Nov 10 2018
%e A305079 The a(315) = 2 connected components of {2,2,3,4} are {{3},{2,2,4}}.
%t A305079 primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A305079 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 A305079 Table[Length[zsm[primeMS[n]]],{n,100}]
%o A305079 (PARI)
%o A305079 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 A305079 A007814(n) = valuation(n,2);
%o A305079 A000265(n) = (n/2^A007814(n));
%o A305079 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 A305079 Cf. A001221, A048143, A056239, A112798, A286518, A286520, A290103, A302242, A303837, A304118, A304714, A304716, A305052, A305055, A305078, A305501.
%K A305079 nonn
%O A305079 1,4
%A A305079 _Gus Wiseman_, May 24 2018
%E A305079 Terms and Mathematica program corrected by _Gus Wiseman_, Nov 10 2018