A227370 -id:A227370 - cp's OEIS frontend

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

Antti Karttunen, Jul 05 2013

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.

			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.

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

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).

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 *)

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)

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)

A227368 a(n) = Index k where A227183(k) for the first time gets value n; the runlength binary code for minimally runlength-encoded unordered partition of size n.

Original entry on oeis.org

0, 1, 2, 5, 4, 9, 8, 17, 16, 23, 32, 39, 40, 71, 72, 87, 80, 151, 144, 167, 160, 295, 288, 327, 320, 351, 576, 607, 640, 671, 672, 1183, 1184, 1311, 1312, 1375, 1344, 2399, 2368, 2655, 2624, 2719, 2688, 4767, 4736, 5279, 5248, 5407, 5376, 5503, 9472, 9599, 10496

Offset: 0

Antti Karttunen, Jul 08 2013

nonn

The word "minimally" in the description means that the integer in whose binary representation some unordered partition of n is encoded should be as small as possible. This sequence gives such a minimal integer for each n, which encodes an unordered partition whose sum is n. The details of the encoding system are explained in A227183.
Also, a(n) gives the index of the first row of A227189/A227739 which sums to n.
Project: Find an algorithm which computes a(n) with a more sophisticated method than just by a blind search. This is a kind of an optimization problem for representing n as a special "bit-packed" sum: the smallest summand of size x costs x bits, and its any subsequent usage in the sum costs just one bit each time. Using any additional summand y > x costs (y-x)+1 bits when used first time, and then again additional usages cost only one bit each. Goal: minimize the number of bits needed. If multiple candidates with the same number of bits are found, then the one which results the smallest integer (when interpreted as a binary number) wins.
For any composite n = t*u, the upper bound for the size of a(n) is t+u-1 bits.
A000267(n) seems to give the binary width of a(n+1). Compare to the conjecture given at A227370.

			   n   a(n)   binary   corresponding partition    sum = n
                       (cf. A227183 for details)
   0     0         0   (0)                          0
   1     1         1   (1)                          1
   2     2        10   (1 + 1)                      2
   3     5       101   (1 + 1 + 1)                  3
   4     4       100   (2 + 2)                      4
   5     9      1001   (1 + 2 + 2)                  5
   6     8      1000   (3 + 3)                      6
   7    17     10001   (1 + 3 + 3)                  7
   8    16     10000   (4 + 4)                      8
   9    23     10111   (3 + 3 + 3)                  9
  10    32    100000   (5 + 5)                     10
  11    39    100111   (3 + 4 + 4)                 11
  12    40    101000   (3 + 3 + 3 + 3)             12
  13    71   1000111   (3 + 5 + 5)                 13
  14    72   1001000   (3 + 3 + 4 + 4)             14
  15    87   1010111   (3 + 3 + 3 + 3 + 3)         15
  16    80   1010000   (4 + 4 + 4 + 4)             16
  17   151  10010111   (3 + 3 + 3 + 4 + 4)         17
  18   144  10010000   (4 + 4 + 5 + 5)             18
  19   167  10100111   (3 + 4 + 4 + 4 + 4)         19
  20   160  10100000   (5 + 5 + 5 + 5)             20
a(5) = 9, because 5 occurs for the first time in A227183 as A227183(9).
Note that for 20, there is for example also a code 175, "10101111" in binary, which results a partition (4 + 4 + 4 + 4 + 4) (= 20), but as 160 < 175, and there are no other partitions of 20 which would result even smaller code number, 160 is the winner (the minimal code), and thus a(20)=160.
A227761 gives the maximum difference between successive parts that occurs in these partitions.

Antti Karttunen, Table of n, a(n) for n = 0..132
Index entries for sequences related to partitions

Same sequence sorted into ascending order: A227369.

Cf. also A227183, A227761, A227762.

def A227368(n):
  '''Index k where A227183(k) for the first time gets value n. A naive implementation.'''
  k = 0
  while(A227183(k) != n): k += 1
  return(k)

a(n) = A227369(A227370(n)) [See comments and conjecture at A227370]

A227369 Positions where A227183 obtains new distinct values for the first time.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 16, 17, 23, 32, 39, 40, 71, 72, 80, 87, 144, 151, 160, 167, 288, 295, 320, 327, 351, 576, 607, 640, 671, 672, 1183, 1184, 1311, 1312, 1344, 1375, 2368, 2399, 2624, 2655, 2688, 2719, 4736, 4767, 5248, 5279, 5376, 5407, 5503, 9472, 9599, 10496

Offset: 0

Antti Karttunen, Jul 08 2013

nonn

Sequence A227368 sorted into ascending order.

Antti Karttunen, Table of n, a(n) for n = 0..132

Cf. A227183, A227368, A227370.

a(n) = A227370(A227368(n)). [See comments and conjectures at A227370]

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A227368 a(n) = Index k where A227183(k) for the first time gets value n; the runlength binary code for minimally runlength-encoded unordered partition of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A227369 Positions where A227183 obtains new distinct values for the first time.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula