A382356 Elimination order of the first person in a variation of the Josephus problem, where there are n people total. During each round the first person is skipped, the second is eliminated and the third person is skipped. Then the process repeats.

1, 2, 3, 2, 4, 4, 3, 5, 7, 4, 10, 9, 5, 14, 9, 6, 10, 15, 7, 18, 21, 8, 19, 14, 9, 15, 24, 10, 21, 28, 11, 23, 19, 12, 20, 26, 13, 31, 28, 14, 36, 24, 15, 25, 43, 16, 47, 39, 17, 44, 29, 18, 30, 44, 19, 40, 50, 20, 42, 34, 21, 35, 45, 22, 57, 47, 23, 55, 39, 24

Offset: 1

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 22 2025

Keywords

• nonn

Comments

This elimination process is related to under-down-under card dealing.

a(3k-2) = k.

Examples

			Consider n people. Four people are in order 1,2,3,4. In the first round, the first person is skipped, the second person is eliminated, and the third person is skipped. Now people are ordered 4,1,3. In the second round, person 4 is skipped, and person 1 is eliminated. Thus, person 1 is eliminated in the second round and a(4) = 2.
		

Crossrefs

Cf. A006257, A225381, A321298, A378635, A382354, A382355, A382358.

Programs

Python

def T(n, A):
    return invPerm(J(n,A))
def J(n,A):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=A[i]
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
def firstPersonElimOrder(n, A):
    return T(n, A)[0]
def UDU(n):
    return [1] + [2 for i in range(n)]
seq = []
for i in range(1,88):
    seq += [firstPersonElimOrder(i, UDU(i))]
print(", ".join([str(v) for v in seq]))

Python

def a(n):
    c, i, J = 1, 0, list(range(1, n+1))
    while len(J) > 0:
        i = (i + 1)%len(J)
        q = J.pop(i)
        if q == 1: return c
        i = (i + 1)%len(J) # skip the third
        c = c+1
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Mar 24 2025