A201144 The pebble sequence: a(n) is the length of the longest non-repeating sequence of pebble-moves among the partitions of n.

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

Offset: 1

Author

N. J. A. Sloane, Nov 27 2011

Keywords

• nonn

Comments

You have n pebbles arranged in several piles. At each turn you take one pebble from each pile and put them into a new pile.

For example, if you start with one pile of 6, at the next step there are two piles: {1,5}, then {2,4}, and so on. Eventually the sequence of partitions will repeat.

Here a(n) is the maximal number of steps before a repeat among all starting partitions.

Examples

			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.
		

Links

• Jorgen Brandt, Cycles of Partitions, Proc. AMS, Vol. 85, No. 3 (July, 1982), pp. 483-486
• Tanya Khovanova and others, Postings to the Sequence Fans Mailing List, circa Nov 18 2009

Crossrefs

For the length of the longest cycle, see A183110. For the length of the shortest cycle, see A054531.

Programs

Mathematica

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}