[seqfan] Re: pebbles sequence

Thu Nov 19 03:43:23 CET 2009

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/