[seqfan] Re: pebbles sequence

[Dion Gijswijt]

Just a small comment: this pebble game is often referred to as `Bulgarian
solitaire'. At least, that is what Martin Gardner called it, when
popularising it in one of his columns from 1983 i think. If I remember
correctly, the lengths of cycles were given in a paper of Jorgen Brandt,
where he also proved that for triangular numbers you always get back to the
position 1+2+..+n.
I don't know about the maximal length in the `tree' to the cycle.

Dion Gijswijt

On Wed, Nov 18, 2009 at 8:47 PM, Tanya Khovanova <
mathoflove-seqfan at yahoo.com> wrote:

> 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.
>
> Here is the coding in Mathematica and the sequence:
>
> In[33]:= << Combinatorica`
> step[list_] := Sort[Select[Prepend[list - 1, Length[list]], # > 0 &]]
> cycleStart[list_] := (res = 1; sofar = {list}; current = list;
>  nextStep = Nest[step, current, 1];
>  While[! MemberQ[sofar, nextStep], res++; current = nextStep;
>   nextStep = Nest[step, current, 1]; sofar = Append[sofar, current]];
>   res)
> Table[Max[Map[cycleStart, Partitions[n]]], {n, 30}]
>
> Out[36]= {1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 13, 13, 14, 19, 21, 21, 18, 19,
> 22, 29, 31, 31, 25, 25, 26, 33, 41, 43, 43, 36}
>
> My problem is that I am not sure which sequence to call the pebble
> sequence, the one I calculated or a(n)+1, when we see the first repetition,
> or the longest sequence of terms before the cycle starts.
>
> I need help with naming and describing these sequences, (not to mention
> that more terms would be nice)
>
> Tanya
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>