A383847 -id:A383847 - cp's OEIS frontend

A383846 A version of the Josephus problem: a(n) is the surviving integer under the eliminate-eliminate-skip version of the elimination process.

1, 2, 3, 3, 3, 6, 6, 3, 9, 6, 3, 9, 6, 12, 9, 15, 12, 18, 15, 3, 18, 6, 21, 9, 24, 12, 27, 15, 3, 18, 6, 21, 9, 24, 12, 27, 15, 30, 18, 33, 21, 36, 24, 39, 27, 42, 30, 45, 33, 48, 36, 51, 39, 54, 42, 3, 45, 6, 48, 9, 51, 12, 54, 15, 57, 18, 60, 21, 63, 24, 66, 27

Offset: 1

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

nonn

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

Cf. A006257, A383845, A383846, A001651, A383847, A337191, A381051.

Consider 4 people in a circle in order 1,2,3,4. In the first round, person 1 is eliminated, then person 2 is eliminated, then person 3 is skipped. Now people are in order 4,3. In the second round, person 4 is eliminated. The last person, person 3, is freed. Thus, a(4) = 3.

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

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.

Original entry on oeis.org

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

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

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.

			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;

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

Cf. A006257, A001651.

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)])

cp's OEIS Frontend

A383846 A version of the Josephus problem: a(n) is the surviving integer under the eliminate-eliminate-skip version of the elimination process.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Python