A346702 The a(n)-th composition in standard order is the odd bisection of the n-th composition in standard order.

0, 1, 2, 1, 4, 2, 1, 3, 8, 4, 2, 5, 1, 3, 6, 3, 16, 8, 4, 9, 2, 5, 10, 5, 1, 3, 6, 3, 12, 6, 3, 7, 32, 16, 8, 17, 4, 9, 18, 9, 2, 5, 10, 5, 20, 10, 5, 11, 1, 3, 6, 3, 12, 6, 3, 7, 24, 12, 6, 13, 3, 7, 14, 7, 64, 32, 16, 33, 8, 17, 34, 17, 4, 9, 18, 9, 36, 18

Offset: 0

Author

Gus Wiseman, Aug 12 2021

Keywords

• nonn

Comments

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

a(n) is the row number in A066099 of the odd bisection of the n-th row of A066099.

Examples

			Composition number 741 in standard order is (2,1,1,3,2,1), with odd bisection (2,1,2), which is composition number 22 in standard order, hence a(741) = 22.
		

Crossrefs

Length of the a(n)-th standard composition is A000120(n)/2 rounded up.

Positions of 1's are A003945.

Positions of 2's (and zero) are A083575.

Sum of the a(n)-th standard composition is A209281(n+1).

Positions of first appearances are A290259.

The version for prime indices is A346703.

The version for even bisection is A346705, with sums A346633.

A000120 and A080791 count binary digits 1 and 0, with difference A145037.

A011782 counts compositions.

A029837 gives length of binary expansion.

A097805 counts compositions by alternating (or reverse-alternating) sum.

A345197 counts compositions by sum, length, and alternating sum.

Cf. A000009, A000302, A000346, A025047, A088218, A124754, A294175, A346697 (reverse: A346699).

Programs

Mathematica

Table[Total[2^Accumulate[Reverse[First/@Partition[Append[ Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse,0],2]]]]/2,{n,0,100}]

Formula

A029837(a(n)) = A209281(n).