A227452 -id:A227452 - 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).

A037481 Base 4 digits are, in order, the first n terms of the periodic sequence with initial period 1,2.

Original entry on oeis.org

0, 1, 6, 25, 102, 409, 1638, 6553, 26214, 104857, 419430, 1677721, 6710886, 26843545, 107374182, 429496729, 1717986918, 6871947673, 27487790694, 109951162777, 439804651110, 1759218604441, 7036874417766, 28147497671065

Offset: 0

Clark Kimberling

The terms have a particular pattern in their binary expansion, which encodes for a "triangular partition" when runlength encoding of unordered partitions are used (please see A129594 for how that encoding works).
  n   a(n)    same in binary           run lengths   unordered partition
    0                 0                    []                    {}
    1                 1                   [1]                   {1}
    6               110                 [2,1]                 {1+2}
   25             11001               [2,2,1]               {1+2+3}
  102           1100110             [2,2,2,1]             {1+2+3+4}
  409         110011001           [2,2,2,2,1]           {1+2+3+4+5}
 1638       11001100110         [2,2,2,2,2,1]         {1+2+3+4+5+6}
 6553     1100110011001       [2,2,2,2,2,2,1]       {1+2+3+4+5+6+7}
26214   110011001100110     [2,2,2,2,2,2,2,1]     {1+2+3+4+5+6+7+8}
104857 11001100110011001   [2,2,2,2,2,2,2,2,1]   {1+2+3+4+5+6+7+8+9}
These partitions are the only fixed points of "Bulgarian Solitaire" operation (see Gardner reference or Wikipedia page), and thus the terms of this sequence give the fixed points for A226062 which implements that operation (using the same encoding for partitions). This also implies that these partitions are the roots of the game trees constructed for decks consisting of 1+2+3+...+k cards. See A227451 for the encoding of the corresponding tops of the main trunks of the same trees. - Antti Karttunen, Jul 12 2013

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Wikipedia, Bulgarian solitaire
Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

Cf. A014985, A015521, A227451.
Cf. A037487 (decimal digits 1,2).
The right edge of the table A227452. The fixed points of A226062.

I:=[0, 1, 6]; [n le 3 select I[n] else 4*Self(n-1)+Self(n-2)-4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 21 2012

LinearRecurrence[{4,1,-4},{0,1,6},40] (* Vincenzo Librandi, Jun 21 2012 *)
Module[{nn=30,ps},ps=PadRight[{},nn,{1,2}];Table[FromDigits[Take[ps,n],4],{n,0,nn}]] (* Harvey P. Dale, Jul 18 2013 *)

concat(0, Vec(x*(2*x+1)/((x-1)*(x+1)*(4*x-1)) + O(x^100))) \\ Colin Barker, Apr 30 2014

a(n) = 2<<(2*n) \ 5; \\ Kevin Ryde, Jun 24 2023

def A037481(n): return (1<<(n<<1|1))//5 # Chai Wah Wu, Jun 28 2023

(define (A037481 n) (/ (- (/ (+ (expt 4 (1+ n)) (expt -1 n)) 5) 1) 2)) ;; Using Ralf Stephan's direct formula - Antti Karttunen, Jul 12 2013

a(n) = ((4^(n+1) - (-1)^(n+1))/5 - 1)/2. - Ralf Stephan
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3). - Vincenzo Librandi, Jun 21 2012
a(n) = A226062(A129594(A227451(n))). [See page 465 in Gardner's book] - Antti Karttunen, Jul 12 2013
G.f.: x*(2*x+1) / ((x-1)*(x+1)*(4*x-1)). - Colin Barker, Apr 30 2014

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

A227451 Number whose binary expansion encodes via runlengths the partition that is at the top of the main trunk of Bulgarian solitaire game tree drawn for the deck with n(n+1)/2 cards.

Original entry on oeis.org

0, 1, 5, 18, 77, 306, 1229, 4914, 19661, 78642, 314573, 1258290, 5033165, 20132658, 80530637, 322122546, 1288490189, 5153960754, 20615843021, 82463372082, 329853488333, 1319413953330, 5277655813325, 21110623253298, 84442493013197, 337769972052786, 1351079888211149

Offset: 0

Antti Karttunen, Jul 12 2013

The terms have particular patterns in their binary expansion, which encodes for an "almost triangular partition" when runlength encoding of unordered partitions are used (please see A129594 for how that encoding works). These are obtained from the perfectly triangular partitions shown in A037481 by inserting 1 to the front of the partition and decrementing the last summand (the largest) by one:
  n   a(n)    same in binary           run lengths   unordered partition
    0                 0                    []                    {}
    1                 1                   [1]                   {1}
    5               101               [1,1,1]               {1+1+1}
   18             10010             [1,2,1,1]             {1+1+2+2}
   77           1001101           [1,2,2,1,1]           {1+1+2+3+3}
  306         100110010         [1,2,2,2,1,1]         {1+1+2+3+4+4}
 1229       10011001101       [1,2,2,2,2,1,1]       {1+1+2+3+4+5+5}
 4914     1001100110010     [1,2,2,2,2,2,1,1]     {1+1+2+3+4+5+6+6}
19661   100110011001101   [1,2,2,2,2,2,2,1,1]   {1+1+2+3+4+5+6+7+7}
78642 10011001100110010 [1,2,2,2,2,2,2,2,1,1] {1+1+2+3+4+5+6+7+8+8}
These partitions occur at the tops of the main trunks of the game trees constructed for decks consisting of 1+2+3+...+k cards. See A037481 for the encoding of the roots of the main trunks of the same trees.

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..1000
Wikipedia, Bulgarian solitaire
Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

Cf. A037481, A182512.

The left edge of the table A227452.

LinearRecurrence[{4,1,-4},{0,1,5,18,77},40] (* Harvey P. Dale, Sep 22 2016 *)

a(n)=if(n<1,0,if(n==1,1,(3*4^n+7*(-1)^n-5)/10)) \\ Ralf Stephan

a(0)=0, a(1)=1, for n>=2, a(n) = A053645(2*A037481(n)) + (1 - (n mod 2)). [Follows from the "insert 1 and decrement the largest part by one" operation on triangular partitions]
Alternatively:
a(0)=0, a(1)=1, and for n>=2, if n is even, then a(n) = 1 + (4*A182512((n-2)/2)) + 2^(2*(n-1)), and if n is odd, then a(n) = 2 + (16*A182512((n-3)/2)) + 2^(2*(n-1)).
From Ralf Stephan, Jul 20 2013: (Start)
a(n) = (1/10) * (3*4^n + 7*(-1)^n - 5).
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3), n>3.
G.f.: (4*x^4 - 3*x^3 + x^2 + x)/((1-x)*(1+x)*(1-4*x)). (End)

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

A037481 Base 4 digits are, in order, the first n terms of the periodic sequence with initial period 1,2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Python

Scheme

Formula

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

A227451 Number whose binary expansion encodes via runlengths the partition that is at the top of the main trunk of Bulgarian solitaire game tree drawn for the deck with n(n+1)/2 cards.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula