A384772 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 first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

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

Offset: 1

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 09 2025

Keywords

• nonn
• tabl

Comments

The numbers 1 through n are arranged in a circle. A pointer starts at position 1. With each turn, the pointer skips three numbers and the next number is eliminated. The process repeats until no numbers remain. This sequence is a concatenation of the rows of the triangle T, where T(n, k) is the elimination order of the k-th number in a circle of n numbers.

This variation of the Josephus problem can equivalently be described in terms of under-under-under-down card dealing, where the cards of a deck are dealt by alternately cycling three cards from the top "under", and then dealing the next card "down". In particular, T(n,k) is the k-th card dealt in under-under-under-down dealing if the deck begins in order 1,2,3,...,n.

Examples

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

Crossrefs

Cf. A378635, A321298, A006257, A225381, A008586, A384770, A088333, A384774.

Programs

Python

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