Vers de Verres -- Can of Worms

For the course Experimental Mathematics, with Doron Zeilberger, we read and discussed the sequence(s) defined by this clever process explained here (click here for rough English translation) by Eric Angelini. During the class peroid, I produced the following depictions of these sequences.

The convention, according to the website, is that a step like 32201 → 02231 → 22310 is a SINGLE step. Thus my diagrams appear different than those on the website -- for some reason, the diagrams on the website do not correspond to the convention.

Images (Apr 12, 2010)

The case n=2

worms

The case n=3

worms

The case n=4

worms

Cases n>4



The Basic Algorithms (Apr 12, 2010)

There are a few easy-to-understand procedures used to compute various data about the "Can of Worms" system. I will outline the algorithm using psuedocode that is (hopefully) easily adaptable to your favorite languages (Maple, Mathematica, C, Pearl, etc.). Please note that most implementations of this will require you to add a "dummy variable" (since these pseudocode algorithms re-assign the value of the input). 
VStep
 Input L (input a list of integers, indexed from 1 to #L)
 k = L[1]
 If #L < k+1
  Then Return FAIL
 L[k+1] = L[k+1] + k
 Remove L[1] from L
 Append 0 to L
 Return L


V
 Input L (as above)
 S = [ ] (an empty list)
 While L not in S
  S = Append L to S
  L = Vstep(L)
  If L = FAIL
   Then Return ( Append FAIL to S )
 End While
 Return S

VC
 Input n (an integer)
 VSP = [ ]
 SP = List of all Lists of length n, with nonnegative integer entries <= n
  (This can be implemented a number of different ways)
 While #SP > 0
  T = V( SP[1] )
  SP = SP - T (This minus is set-complement)
  If T[#T] != FAIL
   Then VSP = Append T to VSP
 End While
 Return VSP

E
 Input n
 ED = [ ]
 SP = List of all Lists of length n, with nonnegative integer entries <= n
 While #SP > 0
  T = V( SP[1] )
  If T[#T] != FAIL
   For i from 1 to #T - 1
    ED = Append [T[i],T[i+1]] to ED
   End For
  End While
 Return ED

WW
 Input n
 WIN = [ ]
 HS = 0
 SP = List of all Lists of length n, with nonnegative integer entries <= n
 While #SP > 0
  T = V( SP[1] )
  SP = SP - T
  If T[#T] != FAIL
   If #T = HS 
    Then WIN = Append T[1] to WIN
   If #T > HS
    Then WIN = [T[1]]
    HS = #T
 End While
 Return [HS,W]


Results (Apr 15, 2010)

The procedure V allows us to recreate the process. The procedure VC allows us to determine all "valid" starting positions for this process. The procedure E allows us to find all edges in the directed graphs representing these systems (as above). The procedure WW allows us to find the longest path(s) in this digraph, as well as the starting point(s) for these path(s).

From all this, we can reproduce some sequences: 
List WW(k)[1] for k=2 to 6

     [2, 4, 7, 10, 13] = Sloane A151986

List #WW(k)[2]] for k=2 to 6

     [1, 2, 4, 9, 38] = Sloane A005204 (????)

List #ValidStartPos(k) for k=2 to 6

     [3, 13, 64, 404, 2135] = Sloane A151987

Suggestions from Dennis Hou (May 2, 2010)

Dennis Hou has suggested to me (April 19, 2010) that log(A151987) may be linear, based on looking at this plot. He has also suggested A176336 and computed the first 8 terms for the "number of unique cycles in the glass worms game with n glasses." Note that his count includes one more than can be idenified in my graphs -- I do not include the 0 worm configuration. I have checked his computations for the terms n=1 through n=6.

It also may be vague, but his count is the number of elements in the cycles -- not the number of cycles. I do not know what "unique cycles" means, but it is not counting cycles, but the number of elements in cycles. The number of cycles (same as the number of connected components) is given by 1, 2, 4, 7, 13, 14, 20, ..., which I have submitted to the OEIS. I have also submitted a correction/suggestion for entry A176336 to fix the wording.