A386643 -id:A386643 - cp's OEIS frontend

A386639 Triangle T(n,k) read by rows, where row n is a permutation of the numbers 1 through n, such that if a deck of n cards is prepared in this order, and the AP dealing is used, then the resulting cards will be dealt in increasing order.

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

Offset: 1

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

The AP dealing is a dealing pattern where x cards are placed at the bottom of the deck, and then the next card is dealt. The number of cards x placed at the bottom changes with every dealt card according to the arithmetic progression 1, 2, 3, and so on. This pattern repeats until all of the cards have been dealt.
This card dealing can equivalently be seen as a variation on the Josephus problem, where one person is skipped, then the next person is eliminated, then two people are skipped and one person is eliminated, then three people are skipped, and so on. T(n,k) is the order of elimination of the k-th person in the Josephus problem. Equivalently, each row of T is the inverse permutation of the corresponding row of the Josephus triangle A386641, i.e., A386641(n,T(n,k)) = k.
The total number of moves for row n is A000096.
The first column is A386643(n), the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A291317(n), corresponding to the index of the freed person in the corresponding Josephus problem.

			Consider a deck of four cards arranged in the order 2,1,4,3. We put one card under and deal the next card, which is card number 1. Now the deck is ordered 4,3,2. We place 2 cards under and deal the next one, which is card number 2. Now the deck is 4,3. Again, placing 3 cards under and dealing the next, we will deal card number 3, leaving card number 4 to be dealt last. The dealt cards are in order. Thus, the fourth row of the triangle is 2,1,4,3.
The triangle begins as follows:
  1;
  2, 1;
  3, 1, 2;
  2, 1, 4, 3;
  3, 1, 4, 5, 2;
  4, 1, 6, 3, 2, 5;
  5, 1, 3, 4, 2, 6, 7;
  3, 1, 7, 5, 2, 6, 8, 4;
  7, 1, 8, 6, 2, 9, 4, 5, 3;

Cf. A000096, A291317, A386641, A386643.

Cf. A378635 (classical elimination process).

T(n,A000096(k)) = k, for A000096(k) <= n.

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

A386305 Numbers of people such that the first person is freed in the variant 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.

Original entry on oeis.org

1, 2, 3, 18, 22, 171, 195, 234, 1262, 2136, 6040, 42545, 353067, 1332099, 1447753, 2789475, 3635021, 7857445, 9224024, 17128159, 27666710, 29279638

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Aug 20 2025

This sequence can also be described in terms of "AP dealing", in which one deals a deck of N cards into a new deck by moving one card to the bottom, dealing out the next card on top of the new deck, moving two cards to the bottom, etc. This sequence consists of all the deck sizes such that the top card remains the same after AP dealing.

Numbers k such that A291317(k) = 1.

			Suppose there are 5 people in a circle. We start with skipping one person and eliminating the next (person number 2). The leftover people are 3,4,5,1 in order. Then we skip two people and eliminate person number 5. The leftover people are 1,3,4 in order. Then we skip three people and person number 1 is eliminated. The leftover people are 3,4 in order. Then we skip four people and eliminate person number 3. Person 4 is freed. As person 1 is not freed, 5 is NOT in this sequence.

Cf. A081614, A291317, A385328, A386312, A386643.

def F(n):
    c, i, J = 1, 0, list(range(1, n+1))
    while len(J) > 1:
        i = (i + c) % len(J)
        q = J.pop(i)
        c = c + 1
    return J[0]
print([n for n in range(1, 100000) if F(n) == 1])

a(20)-a(22) from Jinyuan Wang, Aug 31 2025

cp's OEIS Frontend

A386639 Triangle T(n,k) read by rows, where row n is a permutation of the numbers 1 through n, such that if a deck of n cards is prepared in this order, and the AP dealing is used, then the resulting cards will be dealt in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A386305 Numbers of people such that the first person is freed in the variant 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

Comments

Examples

Crossrefs

Programs

Python

Extensions