A381591 Elimination order of the first person in a variation of the Josephus problem, where there are n people total and two people are skipped each time.

1, 1, 2, 4, 2, 6, 6, 3, 9, 6, 4, 7, 11, 5, 11, 15, 6, 13, 11, 7, 12, 16, 8, 23, 18, 9, 22, 16, 10, 17, 31, 11, 27, 30, 12, 35, 21, 13, 22, 37, 14, 30, 35, 15, 32, 26, 16, 27, 35, 17, 47, 37, 18, 53, 31, 19, 32, 47, 20, 57, 56, 21, 51, 36, 22, 37, 65, 23, 49, 70

Offset

1,3

Comments

a(3k-1) = k.

Links

Table of n, a(n) for n=1..70.

Eric Huang, Tanya Khovanova, Timur Kilybayev, Ryan Li, Brandon Ni, Leone Seidel, Samarth Sharma, Nathan Sheffield, Vivek Varanasi, Alice Yin, Boya Yun, and William Zelevinsky, Card Dealing Math, arXiv:2509.11395 [math.NT], 2025. See p. 17.

Example

Consider n = 4 people. The first person eliminated is number 3. This leaves the remaining people in order 4, 1, 2. The second person eliminated is number 2. Thus, the remaining people in order 4, 1. The next person eliminated is number 4. On the fourth step, person number 1 is eliminated, implying that the order of elimination of the first person is 4: a(4) = 4.

Prog

(Python)
def UUD(n):
    return invPerm(UUDES(n))
def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        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
sequence = []
for i in range(1, 71):
    sequence += [str(UUD(i)[0])]
print(", ".join(sequence))
(Python)
def a(n):
    c, i, J = 1, 0, list(range(1, n+1))
    while len(J) > 0:
        i = (i + 2)%len(J)
        q = J.pop(i)
        if q == 1: return c
        c = c+1
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Mar 24 2025

Crossrefs

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

Sequence in context: A198540 A216369 A083791 * A303347 A382660 A325971

Adjacent sequences: A381588 A381589 A381590 * A381592 A381593 A381594

Keyword

nonn

Author

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

Status

approved