A328512 Number of distinct connected components of the multiset of multisets with MM-number n.

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 3, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2

Offset: 1

Author

Gus Wiseman, Oct 20 2019

Keywords

• nonn

Comments

For n > 1, the first appearance of n is 2 * A080696(n - 1).

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

Examples

			The multiset of multisets with MM-number 1508 is {{},{},{1,2},{1,3}}, which has the 3 connected components {{}}, {{}}, and {{1,2},{1,3}}, two of which are distinct, so a(1508) = 2.
The multiset of multisets with MM-number 12818 is {{},{1,2},{4},{1,3}}, which has the 3 connected components {{}}, {{1,2},{1,3}}, and {{4}}, so a(12818) = 3.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000
• Index entries for sequences related to prime indices in the factorization of n.

Crossrefs

Positions of 0's and 1's are A305078 together with all powers of 2.

Connected numbers are A305078.

Connected components are A305079.

Cf. A007814, A056239, A112798, A286518, A302242, A304714, A304716, A322389, A327076, A328513.

Programs

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[Union[zsm[primeMS[n]]]],{n,100}]

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));
A328512(n) = if(!(n%2), 1+A328512(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, Jan 28 2025

Formula

If n is even, a(n) = A305079(n) - A007814(n) + 1; otherwise, a(n) = A305079(n).

Extensions

Data section extended to a(105) by Antti Karttunen, Jan 28 2025