A227185 -id:A227185 - 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)

A129594 Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n.

Original entry on oeis.org

0, 1, 3, 2, 4, 7, 6, 5, 11, 12, 15, 8, 9, 14, 13, 10, 20, 27, 28, 19, 16, 31, 24, 23, 22, 25, 30, 17, 18, 29, 26, 21, 43, 52, 59, 36, 35, 60, 51, 44, 47, 48, 63, 32, 39, 56, 55, 40, 41, 54, 57, 38, 33, 62, 49, 46, 45, 50, 61, 34, 37, 58, 53, 42, 84, 107, 116, 75, 68, 123

Offset: 0

Antti Karttunen, May 01 2007

This sequence is based on the fact that compositions (i.e. ordered partitions) can be mapped 1-to-1 to partitions by taking the partial sums of the list where one is subtracted from each composant except the first. (See table A227189 where the parts for each partition are listed).
The inverse process, from partitions to compositions, occurs by inserting the first (i.e. smallest) element of a partition sorted into ascending order to the front of the list obtained by adding one to the first differences of the elements.
Compositions map bijectively to nonnegative integers by assigning each run of k consecutive 1's (or 0's) in binary expansion of n with summand k in the composition.
The graph of this sequence is quite interesting.

			a(8) = 11, as 8 is 1000 in binary, mapping to composition 3+1 (we scan the binary expansion from the least to the most significant end), which maps to partition 3+3, whose conjugate-partition is 2+2+2, yielding composition 2+1+1, which maps to binary 1011, 11 in decimal. a(13) = 14, as 13 is 1101 in binary, mapping to composition 1+1+2, which maps to the partition 1+1+2, whose conjugate-partition is 1+3, yielding composition 1+3, which maps to binary 1110, 14 in decimal. a(11) = 8 and a(14) = 13, as taking the conjugate of a partition is a self-inverse operation.

Antti Karttunen, Table of n, a(n) for n = 0..1023
Antti Karttunen, Python-program for computing this and related sequences.
A. Karttunen et al., Run-length encoding, OEIS Wiki.
Index entries for sequences that are permutations of the natural numbers

a(n) = A075158(A122111(1+A075157(n)) - 1). See A129595 for another kind of encoding of integer partitions.
Sequences related to partitions encoded in this way:
Cf. A227189 (parts of partitions listed on separate rows of the array).
Cf. A005811 (number of parts in the partition).
Cf. A136480 (for n>= 1, the smallest part).
Cf. A227185 (the largest part).
Cf. A227183 (sum of parts).
Cf. A227184 (product of parts).
Note that this permutation maps between A005811 and A227185 as follows: A005811(n) = A227185(a(n)) and vice versa: A227185(n) = A005811(a(n)). On the other hand, it keeps A227183 fixed, as A227183(n) = A227183(a(n)).
Cf. also A226062.

A227739 Irregular table where row n lists in nondecreasing order the parts of unordered partition encoded in the runlengths of binary expansion of n; nonzero terms of A227189.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 3, 3, 3, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 1, 3, 4, 4, 4, 1, 3, 3, 1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 2, 4, 1, 1, 3, 1, 4, 5, 5, 5, 1, 4, 4, 1, 1

Offset: 1

Antti Karttunen, Jul 25 2013

Row n has A005811(n) elements. Each row contains a unique (unordered) partition of some integer, and all possible partitions of finite natural numbers eventually occur. The first partition that sums to k occurs at row A227368(k) and the last at row A000225(k).

Other similar tables of unordered partitions: A036036, A036037, A080576, A080577 and A112798.

			Rows are constructed as:
  Row    n in   Runlengths  With one     Partial sums   The row sums
   n    binary  collected   subtracted   of which give  to, i.e. is
                from lsb-   from all     terms on       a partition of
                to msb-end  except 1st   that row       of A227183(n)
   1       "1"        [1]        [1]     1;             1
   2      "10"      [1,1]      [1,0]     1, 1;          2
   3      "11"        [2]        [2]     2;             2
   4     "100"      [2,1]      [2,0]     2, 2;          4
   5     "101"    [1,1,1]    [1,0,0]     1, 1, 1;       3
   6     "110"      [1,2]      [1,1]     1, 2;          3
   7     "111"        [3]        [3]     3;             3
   8    "1000"      [3,1]      [3,0]     3, 3;          6
   9    "1001"    [1,2,1]    [1,1,0]     1, 2, 2;       5
  10    "1010"  [1,1,1,1]  [1,0,0,0]     1, 1, 1, 1;    4
  11    "1011"    [2,1,1]    [2,0,0]     2, 2, 2;       6
  12    "1100"      [2,2]      [2,1]     2, 3;          5
  13    "1101"    [1,1,2]    [1,0,1]     1, 1, 2;       4
  14    "1110"      [1,3]      [1,2]     1, 3;          4
  15    "1111"        [4]        [4]     4;             4
  16   "10000"      [4,1]      [4,0]     4, 4;          8

Antti Karttunen, The rows 1..1023 of the table, flattened

Row sums: A227183, row products: A227184, the initial (smallest) term of each row: A136480, the last (largest) term: A227185.

Cf. also A227189, A227738, A227736.

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

(define (A227739 n) (A227189bi (A227737 n) (A227740 n))) ;; The Scheme-code for A227189bi has been given in A227189.

a(n) = A227189(A227737(n),A227740(n)).

A227189 Square array A(n>=0,k>=0) where A(n,k) gives the (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n, as explained in A227183. The array is scanned antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), etc.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 06 2013

Discarding the trailing zero terms, on each row n there is a unique partition of integer A227183(n). All possible partitions of finite natural numbers eventually occur. The first partition that sums to n occurs at row A227368(n).

Irregular table A227739 lists only the nonzero terms.

			The top-left corner of the array:
row #  row starts as
    0  0, 0, 0, 0, 0, ...
    1  1, 0, 0, 0, 0, ...
    2  1, 1, 0, 0, 0, ...
    3  2, 0, 0, 0, 0, ...
    4  2, 2, 0, 0, 0, ...
    5  1, 1, 1, 0, 0, ...
    6  1, 2, 0, 0, 0, ...
    7  3, 0, 0, 0, 0, ...
    8  3, 3, 0, 0, 0, ...
    9  1, 2, 2, 0, 0, ...
   10  1, 1, 1, 1, 0, ...
   11  2, 2, 2, 0, 0, ...
   12  2, 3, 0, 0, 0, ...
   13  1, 1, 2, 0, 0, ...
   14  1, 3, 0, 0, 0, ...
   15  4, 0, 0, 0, 0, ...
   16  4, 4, 0, 0, 0, ...
   17  1, 3, 3, 0, 0, ...
etc.
8 has binary expansion "1000", whose runlengths are [3,1] (the length of the run in the least significant end comes first) which maps to nonordered partition {3+3} as explained in A227183, thus row 8 begins as 3, 3, 0, 0, ...
17 has binary expansion "10001", whose runlengths are [1,3,1] which maps to nonordered partition {1,3,3}, thus row 17 begins as 1, 3, 3, ...

Antti Karttunen, The first 141 antidiagonals of the table, flattened
Index entries for sequences related to partitions

Only nonzero terms: A227739. Row sums: A227183. The product of nonzero terms on row n>0 is A227184(n). Number of nonzero terms on each row: A005811. The leftmost column, after n>0: A136480. The rightmost nonzero term: A227185.

Cf. A227368 and also arrays A227186 and A227188.

(define (A227189 n) (A227189bi (A002262 n) (A025581 n)))
(define (A227189bi n k) (cond ((< (A005811 n) (+ 1 k)) 0) ((zero? k) (A136480 n)) (else (+ (- (A136480 n) 1) (A227189bi (A163575 n) (- k 1))))))

A227147 Irregular table: palindromic subsections from the rows of array A227141 related to main trunks of game trees drawn for Bulgarian solitaire.

Original entry on oeis.org

1, 1, 3, 1, 2, 4, 3, 2, 3, 4, 2, 3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3, 4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, 5, 5, 6, 4, 5, 7, 6, 6, 6, 6, 5, 6, 7, 6, 6, 6, 5, 6, 6, 7, 6, 6, 5, 6, 6, 6, 7, 6, 5, 6, 6, 6, 6, 7, 5, 6, 8, 7, 7, 7, 7, 7, 6, 7, 8, 7

Offset: 1

Antti Karttunen, Jul 03 2013

Each row n contains A002061(n) terms and is palindromic.

Apart from the last term, each term on row n gives the largest summand in the partitions encountered on the main trunk of the Bulgarian solitaire tree computed for the deck of n(n+1)/2 cards; from row 2 onward, the last term of row k is one less than the largest summand in the unordered triangular partition {1+2+...+k} that is at the root of each game tree of the deck of the same size. The function f(n) = A227185(A227452(n)) would correctly give the largest summand sizes also for those cases.

			Rows 1-6 of the table are:
1
1, 3, 1
2, 4, 3, 2, 3, 4, 2
3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3
4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, 5, 5, 6, 4
5, 7, 6, 6, 6, 6, 5, 6, 7, 6, 6, 6, 5, 6, 6, 7, 6, 6, 5, 6, 6, 6, 7, 6, 5, 6, 6, 6, 6, 7, 5

Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

Antti Karttunen, The rows 1..31 of the table, flattened
Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).

Cf. A227141, A227452, A227185, A227181, A227182.

(define (A227147 n) (A227141bi (A227177 n) (A227181 n))) ;; A227141bi given in A227141.

(define (A227147v2 n) (- (A227185 (A227452 n)) (* (if (> n 1) 1 0) (- (A227177 (+ n 1)) (A227177 n)))))

(define (A227147v3 n) (if (< n 2) n (A005811 (A227452 (- n 1)))))

a(n) = A227141(A227177(n),A227181(n)). [As a sequence. Each row n is a subsequence from the section [n,n^2] of the n-th row of ordinary table A227141.]
;; The following two formulas use the table A227452:
a(n) = A227185(A227452(n)) - ([n>1] * (A227177(n+1) - A227177(n))). [Where the expression [n>1] is an instance of Iverson brackets]
a(n) = n when n<2, otherwise a(n) = A005811(A227452(n-1)).
For all n, a(n) = a(A227182(n)). [This is just a claim that each row is symmetric.]

A092339 Number of adjacent identical digits in the binary representation of n.

Original entry on oeis.org

0, 0, 0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 2, 3, 3, 2, 1, 2, 1, 0, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 4, 3, 2, 3, 2, 1, 2, 3, 2, 1, 0, 1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 5, 4, 3, 4, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 1, 0, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 5, 4, 3, 4, 3, 2

Offset: 0

Ralf Stephan, Mar 18 2004

In binary: number of 00 blocks plus number of 11 blocks. (Note: the blocks can overlap. See the example below.)

			60 in binary is 111100, it has 4 blocks of adjacent digits, so a(60)=4.
Equally, 60's binary Gray code expansion is A003188(60)=34, 100010 in binary, which contains four zeros.

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 84.

Cf. A005811.

a(n)=local(v); v=binary(n); sum(k=1, length(v)-1, v[k]==v[k+1])

a(n)=if(n<1,0,if(n%2==0,a(n/2)+(n>0&&(n/2)%2==0),a((n-1)/2)+((n-1)/2)%2))

(define (A092339 n) (A080791 (A003188 n))) ;; Antti Karttunen, Jul 05 2013

Recurrence: a(2n) = a(n) + [n even], a(2n+1) = a(n) + [n odd].
a(n) = A014081(n) + A056973(n).
For n>0, A227185(n) = a(n)+1.
a(n) = A080791(A003188(n)) [because the sequence gives the number of nonleading zeros in binary Gray code expansion of n] - Antti Karttunen, Jul 05 2013

A278217 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A075159(1+n)) = A046523(1+A075157(n)).

Original entry on oeis.org

1, 2, 2, 4, 6, 2, 4, 8, 12, 6, 2, 6, 12, 4, 8, 16, 24, 12, 6, 30, 6, 2, 6, 12, 36, 12, 4, 12, 24, 8, 16, 32, 48, 24, 12, 60, 30, 6, 30, 60, 12, 6, 2, 6, 30, 6, 12, 24, 72, 36, 12, 60, 12, 4, 12, 36, 72, 24, 8, 24, 48, 16, 32, 64, 96, 48, 24, 120, 60, 12, 60, 180, 60, 30, 6, 30, 210, 30, 60, 120, 24, 12, 6, 30, 6, 2, 6, 12, 60, 30, 6, 30, 60, 12, 24, 48, 144, 72

Offset: 0

Antti Karttunen, Nov 16 2016

nonn

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

Cf. A046523, A075157, A075159, A286617 (rgs-version of this filter).
Other base-2 related filter sequences: A278219, A278222.
Sequences that partition N into same or coarser equivalence classes are at least these: A092339, A227185.

A005811(n) = hammingweight(bitxor(n, n>>1));  \\ This function from Gheorghe Coserea, Sep 03 2015
A286468(n) = { my(p=((n+1)%2), i=0, m=1); while(n>0, if(((n%2)==p), m *= prime(i), p = (n%2); i = i+1); n = n\2); m };
A075157(n) = if(!n,n,(prime(A005811(n))*A286468(n))-1);
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A278217(n) = A046523(1+A075157(n)); \\ From Antti Karttunen, May 17 2017

(define (A278217 n) (A046523 (+ 1 (A075157 n))))
(define (A278217 n) (A046523 (A075159 (+ 1 n))))

a(n) = A046523(1+A075157(n)) = A046523(A075159(1+n)).

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

A129594 Involution of nonnegative integers induced by the conjugation of the partition encoded in the run lengths of binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A227739 Irregular table where row n lists in nondecreasing order the parts of unordered partition encoded in the runlengths of binary expansion of n; nonzero terms of A227189.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A227189 Square array A(n>=0,k>=0) where A(n,k) gives the (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n, as explained in A227183. The array is scanned antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

A227147 Irregular table: palindromic subsections from the rows of array A227141 related to main trunks of game trees drawn for Bulgarian solitaire.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Scheme

Scheme

Scheme

Formula

A092339 Number of adjacent identical digits in the binary representation of n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI

PARI

Scheme

Formula

A278217 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A075159(1+n)) = A046523(1+A075157(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula