A371451 Number of connected components of the binary indices of the prime indices of n.

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

Offset

1,6

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

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.

Links

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

Index entries for sequences related to binary expansion of n.

Index entries for sequences related to prime indices in the factorization of n.

Example

The binary indices of prime indices of 805 are {{1,2},{3},{1,4}}, with 2 connected components {{1,2},{1,4}} and {{3}}, so a(805) = 2.

Mathematica

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
bix[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Table[Length[csm[bix/@prix[n]]], {n, 100}]

Prog

(PARI)
zero_first_elem_and_bitmask_connected_elems(ys) = { my(cs = List([ys[1]]), i=1); ys[1] = 0; while(i<=#cs, for(j=2, #ys, if(ys[j]&&(0!=bitand(cs[i], ys[j])), listput(cs, ys[j]); ys[j] = 0)); i++); (ys); };
A371451(n) = if(1==n, 0, my(cs = apply(p -> primepi(p), factor(n)[, 1]~), s=0); while(#cs, cs = select(c -> c, zero_first_elem_and_bitmask_connected_elems(cs)); s++); (s)); \\ Antti Karttunen, Jan 29 2025

Crossrefs

For prime indices of prime indices we have A305079, ones A305078.

Positions of ones are A325118.

Positions of first appearances are A325782.

For prime indices of binary indices we have A371452, ones A371291.

For binary indices of binary indices we have A326753, ones A326749.

A001187 counts connected graphs.

A007718 counts non-isomorphic connected multiset partitions.

A048143 counts connected antichains of sets.

A048793 lists binary indices, reverse A272020, length A000120, sum A029931.

A070939 gives length of binary expansion.

A112798 lists prime indices, reverse A296150, length A001222, sum A056239.

A326964 counts connected set-systems, covering A323818.

Cf. A000720, A019565, A087086, A096111, A325097, A326782, A368109, A371292, A371294, A371445, A371447.

Sequence in context: A304779 A361691 A334933 * A049100 A276088 A030612

Adjacent sequences: A371448 A371449 A371450 * A371452 A371453 A371454

Keyword

nonn

Author

Gus Wiseman, Apr 01 2024

Extensions

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

Status

approved