[seqfan] Re: pebbles sequence

[drew at math.mit.edu]

A proof that for triangular n the longest cycle has length 1 (and that in 
fact all starting partitions lead to the triangular partition) can be found 
in:

"Cycles of Partitions", Jorgen Brandt, Proc. AMS, Vol. 85, No. 3 (July, 
1982), pp. 483-486,

Cheers,

Drew

On Nov 18 2009, franktaw at netscape.net wrote:

>The limiting pattern for this operation is a triangle.  When n is a 
>triangular number, you just get the triangle.  Otherwise, you get the 
>triangle, with additional values on the diagonal of the next larger 
>triangle; these cycle one step each iteration.  I think I once proved 
>that this is the case, although I don't remember the proof now.  If 
>proved, this proves Drew's conjecture for his second sequence.
>
>Note that this operation is equivalent to picking up the largest pile, 
>and putting one object at a time in the largest piles, creating new 
>piles if you run out.  This operates on the conjugate partition (the 
>"transpose") of the partition Tanya's operation works on.
>
>Franklin T. Adams-Watters
>
>-----Original Message-----
>From: drew at math.mit.edu
>
>Hi Tanya,
>
>This is an interesting problem. I think it actually suggests three
>sequences, one of which appears to already be in the OEIS (but with no
>connection to pebble sequences noted).
>
>First, we have the sequence that you have computed, where a(n) is the
>length of the longest non-repeating sequence of pebble-moves among the
>partitions of n. I would suggest that this is the main 
>"pebble-sequence".
>
>The first 100 terms of this sequence are:
>
>  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, 32, 33, 37, 46, 55, 57, 57, 49, 
>41,
>41, 42, 51, 61, 71, 73, 73, 64, 55, 50, 51, 56, 67, 78, 89, 91, 91, 81, 
>71,
>61, 61, 62, 73, 85, 97, 109, 111, 111, 100, 89, 78, 72, 73, 79, 92, 
>105,
>118, 131, 133, 133, 121, 109, 97, 85, 85, 86, 99, 113, 127, 141, 155, 
>157,
>157, 144, 131, 118, 105, 98, 99, 106, 121
>
>Second, we have the sequence in which a(n) is the length of the longest
>cycle of pebble-moves among the partitions of n.
>
>The first 100 terms of this sequence are:
>
>1, 2, 1, 3, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 6, 6, 6, 6, 6, 1, 7, 7, 7, 
>7,
>7, 7, 1, 8, 8, 8, 8, 8, 8, 8, 1, 9, 9, 9, 9, 9, 9, 9, 9, 1, 10, 10, 10, 
>10,
>10, 10, 10, 10, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 
>12,
>12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 13, 13, 13, 13, 13, 13, 13, 13, 
>13,
>13, 13, 13, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14
>
>which is not in the OEIS, but follows a simple pattern that begs for a
>proof.
>
>Third, we can consider the sequence in which a(n) is the length of the
>shortest cycle of pebble-moves among the partitions of n.
>
>The first 100 terms of this sequence are:
>
>  1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 5, 5, 5, 1, 6, 3, 2, 3, 6, 1, 7, 7, 
>7, 7,
>7, 7, 1, 8, 4, 8, 2, 8, 4, 8, 1, 9, 9, 3, 9, 9, 3, 9, 9, 1, 10, 5, 10, 
>5,
>2, 5, 10, 5, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 6, 
>4, 3,
>12, 2, 12, 3, 4, 6, 12, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 
>13,
>1, 14, 7, 14, 7, 14, 7, 2, 7, 14
>
>which agrees with the first 100 terms of A054531. Obviously this also 
>begs
>for a proof. In any case A054531 probably deserves a comment.
>
>In terms of your original question, based on this data the growth of 
>the
>first sequence is roughly linear in n.
>
>Regards,
>
>Drew
>
>
>On Nov 18 2009, Tanya Khovanova 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/
>>
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>  
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>