A386639 -id:A386639 - cp's OEIS frontend

A386643 Elimination order of the first person in a variation of the Josephus problem in which one person is skipped, then one is eliminated, then two people are skipped and one eliminated, then three people are skipped and so on.

1, 2, 3, 2, 3, 4, 5, 3, 7, 9, 5, 7, 4, 10, 6, 13, 16, 18, 5, 17, 10, 22, 22, 8, 17, 6, 21, 15, 27, 18, 16, 18, 23, 7, 12, 35, 35, 36, 28, 13, 15, 37, 8, 21, 30, 16, 37, 26, 30, 41, 23, 19, 9, 28, 33, 13, 28, 44, 50, 35, 60, 58, 53, 10, 47, 61, 41, 37, 26, 34, 70, 15, 66, 34, 50, 11, 55, 19, 70, 70

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jul 27 2025

nonn

			Consider 4 people in a circle. Initially, person number 1 is skipped, and person 2 is eliminated. The remaining people are now in order 3, 4, 1. Then, two people are skipped, and person 1 is eliminated, implying that the order of elimination of the first person is 2: a(4) = 2.

The first column of triangle A386639.

Cf. A000096, A225381, A386641.

A386641 Triangle read by row: T(n,k) is the number of the k-th eliminated person in a variant of the Josephus problem in which one person is skipped, then one is eliminated, then two people are skipped, then the next person is eliminated and so on.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jul 27 2025

The numbers 1 through n are arranged in a circle. The process starts at position 1. Initially, the first number is skipped, and the next number is eliminated. Then, two numbers are skipped, and the next one is eliminated. Then, three numbers are skipped, and so on. The process repeats until no numbers remain.
This variation of the Josephus problem can equivalently be described in terms of the AP card dealing, where the cards of a deck are dealt by alternately x cards from the top "under", and then dealing the next card "down". Here, x starts as 1, and is increased by 1 with every dealt card. In particular, T(n,k) is the k-th card dealt in the AP dealing if the deck begins in order 1,2,3,...,n.
The freed person is A291317(n).

			Consider 4 people in a circle. Initially, person number 1 is skipped, and person 2 is eliminated. The remaining people are now in order 3, 4, 1. Then, two people are skipped, and person 1 is eliminated. The remaining people are in order 3, 4. Now, three people are skipped and person 4 is eliminated. Person 3 is eliminated last. Thus, the fourth row of the triangle is 2,1,4,3.
The triangle begins as follows:
  1;
  2, 1;
  2, 3, 1;
  2, 1, 4, 3;
  2, 5, 1, 3, 4;
  2, 5, 4, 1, 6, 3;
  2, 5, 3, 4, 1, 6, 7;
  2, 5, 1, 8, 4, 6, 3, 7;
  2, 5, 9, 7, 8, 4, 1, 3, 6;

Cf. A000096, A291317, A386639, A386643.

Cf. A321298 (classical elimination process).

def row(n):
  c, i, J = 1, 0, list(range(1, n+1))
  output = []
  while len(J) > 1:
    i = (i + c) % len(J)
    q = J.pop(i)
    output.append(q)
    c = c + 1
  output.append(J[0])
  return output
print([e for n in range(1,15) for e in row(n)])

T(n,k) = A000096(k), when n >= A000096(k).

cp's OEIS Frontend

A386643 Elimination order of the first person in a variation of the Josephus problem in which one person is skipped, then one is eliminated, then two people are skipped and one eliminated, then three people are skipped and so on.

Views

Author

Keywords

Examples

Crossrefs

A386641 Triangle read by row: T(n,k) is the number of the k-th eliminated person in a variant of the Josephus problem in which one person is skipped, then one is eliminated, then two people are skipped, then the next person is eliminated and so on.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula