A383845 Triangle T(n,k) read by rows: where T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people, where the elimination pattern is eliminate-eliminate-skip.

1, 1, 2, 1, 2, 3, 1, 2, 4, 3, 1, 2, 4, 5, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 7, 3, 6, 1, 2, 4, 5, 7, 8, 6, 3, 1, 2, 4, 5, 7, 8, 3, 6, 9, 1, 2, 4, 5, 7, 8, 10, 3, 9, 6, 1, 2, 4, 5, 7, 8, 10, 11, 6, 9, 3, 1, 2, 4, 5, 7, 8, 10, 11, 3, 6, 12, 9, 1, 2, 4, 5, 7, 8, 10, 11, 13, 3, 9, 12, 6

Offset

1,3

Comments

This Josephus problem is related to down-down-under card dealing.

The n-th row has n elements.

In this variation of the Josephus elimination process, the numbers 1 through n are arranged in a circle. A pointer starts at position 1. With each turn, the pointer eliminates the first number, eliminates the second, then skips the third. The process repeats until no numbers remain. This sequence represents the triangle T(n, k), where n is the number of people in the circle, and T(n, k) is the elimination order of the k-th number in the circle.

Links

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

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 4 people in a circle. Initially, person number 1 is eliminated, person number 2 is eliminated, and person number 3 is skipped. The remaining people are now in order 4, 3. Then, both are eliminated. Thus, the fourth row of the triangle is 1, 2, 4, 3, the order of elimination.
The triangle begins
  1;
  1, 2;
  1, 2, 3;
  1, 2, 4, 3;
  1, 2, 4, 5, 3;
  1, 2, 4, 5, 3, 6;
  1, 2, 4, 5, 7, 3, 6;
  1, 2, 4, 5, 7, 8, 6, 3;

Prog

(Python)
def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = i%len(J)
        out.append(J.pop(i))
        i = i%len(J)
        if len(J) > 1:
            out.append(J.pop(i))
        i = (i + 1)%len(J)
    out += [J[0]]
    return out
print([e for n in range(1, 14) for e in row(n)])

Crossrefs

Cf. A383846 (row end), A383847 (inverse permutation), A384753 (permutation order).

Cf. A006257, A001651.

Sequence in context: A370263 A376308 A380911 * A194976 A195082 A210535

Adjacent sequences: A383842 A383843 A383844 * A383846 A383847 A383848

Keyword

nonn,tabl

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, May 12 2025

Status

approved