A227147 -id:A227147 - cp's OEIS frontend

A226062 a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.

0, 1, 3, 2, 13, 7, 6, 6, 11, 29, 15, 58, 9, 14, 4, 14, 19, 27, 61, 54, 245, 31, 122, 52, 27, 25, 30, 50, 25, 12, 12, 30, 35, 23, 59, 46, 237, 125, 118, 44, 235, 501, 63, 1002, 233, 250, 116, 40, 51, 19, 57, 38, 229, 62, 114, 36, 59, 17, 28, 34, 57, 8, 28, 62

Offset: 0

Antti Karttunen, Jul 06 2013

For this sequence the partitions are encoded in the binary expansion of n in the same way as in A129594.
In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them. The question originally posed was: on what condition the resulting partitions will eventually reach a fixed point, that is, a collection of piles that will be unchanged by the operation. See Martin Gardner reference and the Wikipedia-page.
A037481 gives the fixed points of this sequence, which are numbers that encode triangular partitions: 1 + 2 + 3 + ... + n.
A227752(n) tells how many times n occurs in this sequence, and A227753 gives the terms that do not occur here.
Of further interest: among each A000041(n) numbers j_i: j1, j2, ..., jk for which A227183(j_i)=n, how many cycles occur and what is the size of the largest one? (Both are 1 when n is in A000217, as then the fixed points are the only cycles.) Cf. A185700, A188160.
Also, A123975 answers how many Garden of Eden partitions there are for the deck of size n in Bulgarian Solitaire, corresponding to values that do not occur as the terms of this sequence.

			5 has binary expansion "101", whose runlengths are [1,1,1], which are converted to nonordered partition {1+1+1}.
6 has binary expansion "110", whose runlengths are [1,2] (we scan the runs of bits from right to left), which are converted to nonordered partition {1+2}.
7 has binary expansion "111", whose list of runlengths is [3], which is converted to partition {3}.
In "Bulgarian Operation" we subtract one from each part (with 1-parts vanishing), and then add a new part of the same size as there originally were parts, so that the total sum stays same.
Thus starting from a partition encoded by 5, {1,1,1} the operation works as 1-1, 1-1, 1-1 (all three 1's vanish) but appends part 3 as there originally were three parts, thus we get a new partition {3}. Thus a(5)=7.
From the partition {3} -> 3-1 and 1, which gives a new partition {1,2}, so a(7)=6.
For partition {1+2} -> 1-1 and 2-1, thus the first part vanishes, and the second is now 1, to which we add the new part 2, as there were two parts originally, thus {1+2} stays as {1+2}, and we have reached a fixed point, a(6)=6.

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, Table of n, a(n) for n = 0..8191
Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).
Antti Karttunen, Python-program for computing this and related sequences.
Wikipedia, Bulgarian solitaire

Cf. A227147, A227183, A227452.
Cf. A037481 (gives the fixed points).
Cf. A227752 (how many times n occurs here).
Cf. A227753 (numbers that do not occur here).
Cf. A129594 (conjugates the partitions encoded with the same system).
Cf. also A123975, A074909, A185700, A071762, A075157, A075158, A243353, A243354, A242424, A243051.

Other identities:
A227183(a(n)) = A227183(n). [This operation doesn't change the total sum of the partition.]
a(n) = A243354(A242424(A243353(n))).
a(n) = A075158(A243051(1+A075157(n))-1).

A227185 The largest part in the unordered partition encoded in the runlengths of the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 2, 3, 3, 2, 1, 2, 3, 2, 3, 4, 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, 5, 4, 3, 4, 3, 2, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 6, 5, 4, 5, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 2, 1, 2

Offset: 0

Antti Karttunen, Jul 05 2013

The bijective encoding of nonordered partitions via compositions (ordered partitions) present in the binary expansion of n is explained in A227184.

It appears that a(4n+2) = a(2n+1). - Ralf Stephan, Jul 20 2013

			12 has binary expansion "1100", for which the lengths of runs (consecutive blocks of 0- or 1-bits) are [2,2]. Converting this to a partition in the manner explained in A227184 gives the partition {2+3}. Its largest part is 3, thus a(12)=3, which is actually the first time when this sequence differs from A043276.

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

For all n, A005811(n) = a(A129594(n)). Cf. also A136480 (for n>= 1, gives the smallest part) and A227183, A227184, A226062, A092339, A227147.

a(n) gives the rightmost nonzero term on the n-th row of A227189.

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

(define (A227185 n) (if (zero? n) n (+ 1 (- (A029837 (+ 1 n)) (A005811 n)))))
(define (A227185v2 n) (if (zero? n) n (car (reverse (binexp_to_ascpart n))))) ;; Alternative definition, using the auxiliary functions given in A227184.

Defining formula:
a(0)=0; and for n>=1, a(n) = A029837(n+1) - (A005811(n)-1). [Because the largest part in the unordered partition in this encoding scheme is computed as (c_1 + (c_2-1) + (c_3-1) + ... + (c_k-1)) where c_1 .. c_k are the parts of the k-part composition that sum together as c_1 + c_2 + ... + c_k = A029837(n+1) (the binary width of n), so we subtract from the total binary width of n the number of runs (A005811) minus 1.]
Equivalently: a(n) = A092339(n)+1 for n>0.
a(n) = A005811(A129594(n)). [This just states the fact that when conjugating a partition, the largest part of an old partition will be the number of the parts in the new, conjugated partition.]

A227177 n occurs n^2 - n + 1 times.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 03 2013

nonn

a(n) is the least integer k such that A006527(k) >= n, which implies that each n occurs A002061(n) times.

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

Cf. A000196, A002061, A006527, A227179, A227181, A227147.

Flatten[Map[ConstantArray[#,(#-2) (#-1)+1]-1&,Range[7]]] (* Peter J. C. Moses, Jul 14 2013 *)
Flatten[Table[#,{#^2-#+1}]&/@Range[0,7]] (* Harvey P. Dale, Sep 25 2013 *)

vec(N)=concat(vector(N, i, vector(i^2-i+1, j, i))) \\ Jinyuan Wang, Dec 01 2018

from sympy import integer_nthroot
def A227177(n): return (m:=integer_nthroot(k:=3*n,3)[0])+(k>m*(m**2+2)) # Chai Wah Wu, Nov 07 2024

a(k + (j^3-j^2+5*j)/3) = j for all j>=0, k=0..(j^2-j). - Jinyuan Wang, Nov 24 2018

a(n) = m+1 if 3n>m*(m^2+2) and a(n) = m otherwise where m=floor((3n)^(1/3)). - Chai Wah Wu, Nov 07 2024

A227452 Irregular table where each row lists the partitions occurring on the main trunk of the Bulgarian Solitaire game tree (from the top to the root) for deck of n(n+1)/2 cards. Nonordered partitions are encoded in the runlengths of binary expansion of each term, in the manner explained in A129594.

Original entry on oeis.org

0, 1, 5, 7, 6, 18, 61, 8, 11, 58, 28, 25, 77, 246, 66, 55, 36, 237, 226, 35, 46, 116, 197, 115, 102, 306, 985, 265, 445, 200, 155, 946, 905, 285, 220, 145, 475, 786, 925, 140, 185, 465, 395, 826, 460, 409, 1229, 3942, 1062, 1782, 1602, 823, 612, 3789, 3622, 1142

Offset: 0

Antti Karttunen, Jul 12 2013

The terms for row n are computed as A227451(n), A226062(A227451(n)), A226062(A226062(A227451(n))), etc. until a term that is a fixed point of A226062 is reached (A037481(n)), which will be the last term of row n.

Row n has A002061(n) = 1,1,3,7,13,21,... terms.

			Rows 0 - 5 of the table are:
0
1
5, 7, 6
18, 61, 8, 11, 58, 28, 25
77, 246, 66, 55, 36, 237, 226, 35, 46, 116, 197, 115, 102
306, 985, 265, 445, 200, 155, 946, 905, 285, 220, 145, 475, 786, 925, 140, 185, 465, 395, 826, 460, 409

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, Rows 0-31 of table, flattened

Left edge A227451. Right edge: A037481. Cf. A227147 (can be computed from this sequence).

;; with Antti Karttunen's IntSeq-library for memoizing definec-macro
;; Compare with the other definition for A218616:
(definec (A227452 n) (cond ((< n 2) n) ((A226062 (A227452 (- n 1))) => (lambda (next) (if (= next (A227452 (- n 1))) (A227451 (A227177 (+ 1 n))) next)))))
;; Alternative implementation using nested cached closures for function iteration:
(define (A227452 n) ((compose-A226062-to-n-th-power (A227179 n)) (A227451 (A227177 n))))
(definec (compose-A226062-to-n-th-power n) (cond ((zero? n) (lambda (x) x)) (else (lambda (x) (A226062 ((compose-A226062-to-n-th-power (- n 1)) x))))))

For n < 2, a(n) = n, and for n>=2, if A226062(a(n-1)) = a(n-1) [in other words, when a(n-1) is one of the terms of A037481] then a(n) = A227451(A227177(n+1)), otherwise a(n) = A226062(a(n-1)).

Alternatively, a(n) = value of the A227179(n)-th iteration of the function A226062, starting from the initial value A227451(A227177(n)). [See the other Scheme-definition in the Program section]

A227181 Irregular table: integers from n to n^2 followed by integers from (n+1) to (n+1)^2.

Original entry on oeis.org

0, 1, 2, 3, 4, 3, 4, 5, 6, 7, 8, 9, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36

Offset: 0

Antti Karttunen, Jul 03 2013

			Row n is A002061(n) terms long, and contains successive integers from n to n*n:
  0;
  1;
  2, 3, 4;
  3, 4, 5, 6, 7, 8, 9;
  4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
  ...

Antti Karttunen, Rows 0..31, flattened

Right edge: A000290. Central diagonal: A000217. Cf. also A227147.

Flatten[(#+Range[(#1-2) (#1-1)+1]-2&)[Range[7]]] (* Peter J. C. Moses, Jul 11 2013 *)
Table[Range[n,n^2],{n,0,6}]//Flatten (* Harvey P. Dale, Apr 03 2021 *)

from sympy import integer_nthroot
def A227181(n): return n-(r:=(m:=integer_nthroot(k:=3*n,3)[0])-(k<=m*(m**2+2)))*(r**2-1)//3 # Chai Wah Wu, Nov 07 2024

(define (A227181 n) (+ (A227177 n) (A227179 n)))

a(n) = A227177(n)+ A227179(n). [As a sequence].

A227182 Simple self-inverse permutation of natural numbers: List each block of n^2 - n + 1 numbers from ((n-1)^3 + 2(n-1))/3 + 1 to (n^3 + 2n)/3 in reverse order.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 04 2013

nonn

In other words, after zero, list each block of A002061(n) numbers from A116731(n) to A006527(n) in reverse order.

Antti Karttunen, Table of n, a(n) for n = 0..9951
Index entries for sequences that are permutations of the natural numbers

Cf. A227177, A227179, A227147.

Flatten[(Reverse/@( (-1+#) (9-5 #+#^2)/3+Range[(#-2) (#-1)+1]-1)&)[Range[7]]] (* Peter J. C. Moses, Jul 11 2013 *)

(define (A227182 n) (- (A006527 (A227177 n)) (A227179 n)))

a(n) = A006527(A227177(n)) - A227179(n).

A227141 Array A(n,k) where A(1,k)=1 for row 1, and subsequent rows A(n > 1, k) are computed by recurrences related to Bulgarian Solitaire; square array A(n,k), with row n >= 1, column k >= 0, read by antidiagonals.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 03 2013

The initial terms give the summands of the partitions (or: number of parts, when shifted once) that occur in the main trunk of Bulgarian solitaire tree computed for a pack containing 1+2+...+n cards.

The irregular table A227147 gives just the palindromic subsequence from each row. After that part, the recurrence on row n always leads to a sequence of period n.

			The top left corner of the array begins
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...
1, 1, 2, 2, 4, 3, 2, 3, 4, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, ...
1, 1, 2, 3, 3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3, 4, 4, 4, 3, 4, ...
1, 1, 2, 3, 4, 4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, ...
...
For row 3, the recurrence manifests itself as:
a_3(0) = 1; a_3(0<n<3) = n (i.e., a_3(1)=1, a_3(2)=2), a_3(3) = 2, a_3(4) = 4, a_3(4<n<6) (that is, a_3(5)) = 3, and after that, for values n>=6, a_3(n) = the least natural number k such that a_3(n-k-1) < k+1.
As a_3(6-0-1) = a_3(5) = 3 is not less than 1, nor a_3(6-1-1) = a_3(4) = 2 is not less than 2, but a_3(6-2-1) = a_3(3) = 2 IS less than 3 (2+1), the sought value of k is 2, and a_3(6)=2.

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 first 99 antidiagonals of the table, flattened
Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).

Cf. A227147.

The recurrence for the r-th row of the table (after the first row, which contains a constant sequence A000012) is defined as follows:
a_r(0) = 1; a_r(0=2r), a_r(n) = the least natural number k such that a_r(n-k-1) < k+1.
See also the given Scheme program.

cp's OEIS Frontend

A226062 a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A227185 The largest part in the unordered partition encoded in the runlengths of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A227177 n occurs n^2 - n + 1 times.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Scheme

Formula

A227181 Irregular table: integers from n to n^2 followed by integers from (n+1) to (n+1)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A227182 Simple self-inverse permutation of natural numbers: List each block of n^2 - n + 1 numbers from ((n-1)^3 + 2*(n-1))/3 + 1 to (n^3 + 2*n)/3 in reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A227141 Array A(n,k) where A(1,k)=1 for row 1, and subsequent rows A(n > 1, k) are computed by recurrences related to Bulgarian Solitaire; square array A(n,k), with row n >= 1, column k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A227182 Simple self-inverse permutation of natural numbers: List each block of n^2 - n + 1 numbers from ((n-1)^3 + 2(n-1))/3 + 1 to (n^3 + 2n)/3 in reverse order.