cp's OEIS Frontend

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

%I A201144 #20 Dec 23 2024 14:53:42
%S A201144 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,
%T A201144 33,41,43,43,36,32,33,37,46,55,57,57,49,41,41,42,51,61,71,73,73,64,55,
%U A201144 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
%N A201144 The pebble sequence: a(n) is the length of the longest non-repeating sequence of pebble-moves among the partitions of n.
%C A201144 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.
%C A201144 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.
%C A201144 Here a(n) is the maximal number of steps before a repeat among all starting partitions.
%H A201144 Jorgen Brandt, <a href="http://dx.doi.org/10.1090/S0002-9939-1982-0656129-5">Cycles of Partitions</a>, Proc. AMS, Vol. 85, No. 3 (July, 1982), pp. 483-486
%H A201144 Tanya Khovanova and others, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2009-November/002937.html">Postings to the Sequence Fans Mailing List</a>, circa Nov 18 2009
%e A201144 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.
%t A201144 In[33]:= << Combinatorica`
%t A201144 step[list_] := Sort[Select[Prepend[list - 1, Length[list]], # > 0 &]]
%t A201144 cycleStart[list_] := (res = 1; sofar = {list}; current = list;
%t A201144 nextStep = Nest[step, current, 1];
%t A201144 While[! MemberQ[sofar, nextStep], res++; current = nextStep;
%t A201144   nextStep = Nest[step, current, 1]; sofar = Append[sofar, current]];
%t A201144   res)
%t A201144 Table[Max[Map[cycleStart, Partitions[n]]], {n, 30}]
%t A201144 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}
%Y A201144 For the length of the longest cycle, see A183110. For the length of the shortest cycle, see A054531.
%K A201144 nonn
%O A201144 1,2
%A A201144 _N. J. A. Sloane_, Nov 27 2011