A227183 a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.

0, 1, 2, 2, 4, 3, 3, 3, 6, 5, 4, 6, 5, 4, 4, 4, 8, 7, 6, 8, 8, 5, 7, 9, 7, 6, 5, 7, 6, 5, 5, 5, 10, 9, 8, 10, 10, 7, 9, 11, 12, 9, 6, 10, 11, 8, 10, 12, 9, 8, 7, 9, 9, 6, 8, 10, 8, 7, 6, 8, 7, 6, 6, 6, 12, 11, 10, 12, 12, 9, 11, 13, 14, 11, 8, 12, 13, 10, 12, 14

Offset: 0

Author

Antti Karttunen, Jul 05 2013

Keywords

• nonn
• base
• look

Comments

Like A129594 this sequence utilizes the fact that compositions (i.e., ordered partitions) can be bijectively mapped to (unordered) partitions by taking the partial sums of the list of composants after one has been subtracted from each except the first one. Compositions in turn are mapped to nonnegative integers via the runlength encoding, where the lengths of maximum runs of 0's or 1's in binary representation of n give the composants. See the OEIS Wiki page and the example below.

Each n occurs A000041(n) times in total and occurs for the first time at A227368(n) and for the last time at position A000225(n). See further comments and conjectures at A227368 and A227370.

Examples

			19 has binary expansion "10011", thus the maximal runs of identical bits (scanned from right to left) are [2,2,1]. We subtract one from each after the first one, to get [2,1,0] and then form their partial sums as [2,2+1,2+1+0], which thus maps to unordered partition {2+3+3} which adds to 8. Thus a(19)=8.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8192
• A. Karttunen et al., Run-length encoding, OEIS Wiki.
• Index entries for sequences related to partitions

Crossrefs

Row sums of A227189 and A227739. Cf. A227184 (corresponding products), A227185, A227189, A227192, A129594, A226062, A227368.

Analogous sum sequences computed for other encoding schemes of unordered partitions: A036042, A056239, A161511, A243503. Cf. also A229119, A003188, A075157, A243353 (associated permutations mapping between these schemes).

Programs

Mathematica

Table[Function[b, Total@ Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b] - Boole[n == 0]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 0, 79}] // Flatten (* Michael De Vlieger, May 09 2017 *)

Python

def A227183(n):
  '''Sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n.'''
  s = 0
  b = n%2
  i = 1
  while (n != 0):
    n >>= 1
    if ((n%2) == b): # Staying in the same run of bits?
      i += 1
    else: # The run changes.
      b = n%2
      s += i
  return(s)

Formula

a(n) = Sum_{i=0..A005811(n)-1} A227189(n,i). [The defining formula]

Equivalently, for n>=1, a(n) = Sum_{i=(A173318(n-1)+1)..A173318(n)} A227739(i).

a(n) = A227192(n) - A000217(A005811(n)-1).

Other identities:

a(A129594(n)) = a(n). [This follows from the fact that conjugating a partition doesn't change its total sum]

a(A226062(n)) = a(n). [Which is also true for the "Bulgarian operation"]

From Antti Karttunen, Mar 08 2015: (Start)

Can be also obtained by mapping with an appropriate permutation from the sequences giving sizes of each partition (i.e., sum of their parts) computed for other enumerations similar to A227739:

a(n) = A036042(A229119(n)).

a(n) = A161511(A003188(n)).

a(n) = A056239(A243353(n)).

a(n) = A243503(1+A075157(n)).

(End)