[seqfan] pebbles sequence

William Marshall w.r.marshall at actrix.co.nz
Thu Nov 19 07:20:38 CET 2009

> From: Tanya Khovanova

> Hello Sequence Fans,
>
> I suggest to add pebble sequences based on the famous pebble problem:
>
> You have 45 pebbles arranged in several piles. Each turn you take one pebble from each pile and put them into a new pile. What is an asymptotic behavior for this process?
>
> For example, if you start with one pile of 6, next step will be two piles: {1,5}, then {2,4} and so on. Eventually the sequence of partitions will start repeating itself.
>
> The sequence I calculated is the following: given n - the number of pebbles we take a partition and apply the operation above until we see a partition that we saw before. The sequence is the number of steps we need until the sequence repeats itself for the worst partition.
>
> For example, for n = 6, the worst case is {2,2,1,1}, and the steps are: {2, 2, 1, 1}, {1, 1, 4}, {3, 3}, {2, 2, 2}, {1, 1, 1, 3}, {2, 4}, {1,
>   2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}. Hence a(6) = 7.

Starting with {2,2,1,1}, you actually only apply the operation six times to reach {1,2,3} (although you run through seven partitions). When n is the k-th triangular number, the maximum number of operations is k*(k-1), ending in a cycle of 1.

[...]

> I need help with naming and describing these sequences, (not to mention that more terms would be nice)

What you describe is known as Bulgarian solitaire.

A relevant sequence in the OEIS is the number of partitions of n that have no "parent" in Bulgarian solitaire:

http://www.research.att.com/~njas/sequences/A123975