A381048 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, and the second and the third person are eliminated. Then the process repeats.

1, 2, 3, 3, 4, 6, 5, 6, 9, 7, 8, 11, 9, 10, 14, 11, 12, 18, 13, 14, 19, 15, 16, 22, 17, 18, 27, 19, 20, 27, 21, 22, 30, 23, 24, 35, 25, 26, 35, 27, 28, 38, 29, 30, 44, 31, 32, 43, 33, 34, 46, 35, 36, 54, 37, 38, 51, 39, 40, 54, 41, 42, 61, 43, 44, 59, 45, 46, 62, 47

Offset: 1

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Apr 14 2025

Keywords

• nonn

Comments

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

Examples

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

Crossrefs

Cf. A006257, A007494, A225381, A321298, A378635, A337191, A381049, A382528.

Programs

Python

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

Formula

a(3k+1) = 2k+1; a(3k-1) = 2k.