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

Author

Antti Karttunen, Jul 06 2013

Keywords

• nonn
• base

Comments

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.

Examples

			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.
		

References

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

Links

• 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

Crossrefs

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.

Formula

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