Properties of the "eeny, meeny, miny, moe function"

147 Views Asked by At

N.B.: there's another question about "eeny, meeny, miny, moe" in mathstackexchange but it is different to what it is presented here.

Consider the function $f(p,s)$ defined as follows:

  1. There are $p>1$ players.
  2. We use a rhyme with $s>1$ steps.
  3. We start by player 1 and we apply the rhyme. The player where the rhyme ends is eliminated (cycling around if needed).
  4. Step 3 is repeated starting with the next non-eliminated player.
  5. The last standing player is $f(p,s)$.

So, for example, if $p=5$ and $s=3$ we would eliminate players 3, 1, 5 and 2 in that order and we get $f(5,3)=4$.

You can implement this function in Python as:

def f(p,s):
    P=range(p)
    while len(P)>1:
        r=s%len(P)
        if r==0:
            r=len(P)
        P=P[r:]+P[:r-1]
    return P[0]+1

Using this, it is easy to get a table with some values (I include up to 16 here):

    s  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
  p   --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --
  1|   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
  2|   2   1   2   1   2   1   2   1   2   1   2   1   2   1   2   1
  3|   3   3   2   2   1   1   3   3   2   2   1   1   3   3   2   2
  4|   4   1   1   2   2   3   2   3   3   4   4   1   4   1   1   2
  5|   5   3   4   1   2   4   4   1   2   4   5   3   2   5   1   3
  6|   6   5   1   5   1   4   5   3   5   2   4   3   3   1   4   1
  7|   7   7   4   2   6   3   5   4   7   5   1   1   2   1   5   3
  8|   8   1   7   6   3   1   4   4   8   7   4   5   7   7   4   3
  9|   9   3   1   1   8   7   2   3   8   8   6   8   2   3   1   1
 10|  10   5   4   5   3   3   9   1   7   8   7  10   5   7   6   7
 11|  11   7   7   9   8   9   5   9   5   7   7  11   7  10  10   1
 12|  12   9  10   1   1   3  12   5   2   5   6  11   8  12   1   5
 13|  13  11  13   5   6   9   6  13  11   2   4  10   8  13   3   8
 14|  14  13   2   9  11   1  13   7   6  12   1   8   7  13   4  10
 15|  15  15   5  13   1   7   5  15  15   7  12   5   5  12   4  11
 16|  16   1   8   1   6  13  12   7   8   1   7   1   2  10   3  11

Apart from the obvious properties $f(1,s)=1$, $f(p,1)=p$ and $f(p,p)=f(p-1,p)$, I was only able to see the cyclic pattern that repeats in rows 2 and 3 (so for 2 or 3 players), but not much more than that.

My questions are:

  1. Is there any general pattern of the sort $f(p,s+k(p))=f(p,s)$?
  2. Is there any other relevant property of the function $f$ that I'm missing?
  3. More in general, does this function have any particular name and is used somewhere else in Mathematics?

Edit: As for the first question it seems now clear to me that $f(p,s+p!)=f(p,s)$.