A381050 -id:A381050 - cp's OEIS frontend

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

1, 2, 2, 2, 5, 5, 2, 8, 5, 2, 8, 5, 11, 8, 14, 11, 17, 14, 2, 17, 5, 20, 8, 23, 11, 26, 14, 2, 17, 5, 20, 8, 23, 11, 26, 14, 29, 17, 32, 20, 35, 23, 38, 26, 41, 29, 44, 32, 47, 35, 50, 38, 53, 41, 2, 44, 5, 47, 8, 50, 11, 53, 14, 56, 17, 59, 20, 62, 23, 65, 26, 68

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Apr 14 2025

nonn

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

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

Cf. A006257, A032766, A225381, A321298, A378635, A381050, A383076.

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

A378674 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and down-under dealing is used, then the resulting cards are put down in increasing order.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova and the MIT PRIMES STEP junior group, Dec 03 2024

Down-under dealing is a dealing pattern where the top card is dealt then the next card is put on the bottom of the deck. Then, this pattern repeats until all cards are dealt.
This card dealing is related to a variation of the Josephus problem, where the first person is eliminated and the second person is skipped. The card in row n and column k is x if and only if in the Josephus problem variation with n people, the person number x is the k-th person eliminated. Equivalently, each row of the Josephus triangle A378682 related to this variation is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is 2n-1.
The first column is the order of elimination of the first person in the corresponding variation of the Josephus problem and consists of all ones.
The index of the largest number in row n is A152423(n), corresponding to the index of the freed person in this variation of the Josephus problem.
T(n,2j-1) = j, for 2j-1 <= n.
Sequence A378635 represents a similar triangle for under-down dealing.

			Suppose there are four cards arranged in order 1,3,2,4. Card 1 is dealt, and card 3 goes under, then card 2 is dealt, and card 4 goes under. Now, the leftover deck is ordered 3,4. Card 3 is dealt, and card 4 goes under. Now, the leftover deck is card 4, which is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,3,2,4.
Triangle begins:
  1;
  1, 2;
  1, 3, 2;
  1, 3, 2, 4;
  1, 5, 2, 4, 3;
  1, 4, 2, 6, 3, 5;
  1, 6, 2, 5, 3, 7, 4;
  1, 5, 2, 7, 3, 6, 4, 8;
  1, 9, 2, 6, 3, 8, 4, 7, 5;

Cf. A006257, A152423, A225381, A321298, A378635, A378682, A381050.

row[n_] := Module[{ds, res, k, i = 1, len}, ds = CreateDataStructure["Queue", Range[n]]; res = CreateDataStructure["FixedArray", n]; While[(ds["Length"] >= 2), res["SetPart", i++, ds["Pop"]]; ds["Push", ds["Pop"]];]; res["SetPart", n, ds["Pop"]]; Flatten[PositionIndex[res["Elements"]] /@ Range[n]]]; Array[row, 14, 1] // Flatten (* Shenghui Yang, May 16 2025 *)

T(1,1) = 1, for n > 1, T(n,1) = 1 and T(n,2) = T(n-1,n-1) + 1. For n > 1 and k > 2, T(n,k) = T(n-1,k-2) + 1.
From Pontus von Brömssen, Dec 11 2024: (Start)
T(n,k) = A378635(n-1,k-1) + 1 for 2 <= k <= n.
T(n,k) = A378635(n,(k mod n) + 1).
(End)

A383076 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-skip-eliminate.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Apr 15 2025

This Josephus problem is related to down-under-down 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, skips the second, then eliminates 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 skipped, and person number 3 is eliminated. The remaining people are now in order 4, 2. Then, 4 is eliminated, and 2 is left. Thus, the fourth row of the triangle is 1, 3, 4, 2, the order of elimination.
Triangle begins;
1;
1, 2;
1, 3, 2;
1, 3, 4, 2;
1, 3, 4, 2, 5;
1, 3, 4, 6, 2, 5;
1, 3, 4, 6, 7, 5, 2;
1, 3, 4, 6, 7, 2, 5, 8;

Cf. A006257, A032766, A225381, A321298, A378635, A381050, A381051.

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 + 1)%len(J)
        if len(J) > 1:
            out.append(J.pop(i))
    out += [J[0]]
    return out
print([e for n in range(1, 14) for e in row(n)]) # Michael S. Branicky, Apr 28 2025

A383847 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 down-down-under dealing is used, then the resulting cards will be dealt in increasing order.

Original entry on oeis.org

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

Offset: 1

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

Down-down-under dealing is a dealing pattern where the top two cards are dealt, then the third card is placed at the bottom of the deck. This pattern repeats until all of the cards have been dealt.
This card dealing is related to a variation on the Josephus problem, where the first two people are eliminated, and the third person is skipped. The card in row n and column k is x if and only if in the corresponding Josephus problem with n people, the person number x is the k-th person eliminated. Equivalently, each row of Josephus triangle A383845 is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is A001651(n) = floor((3*n-1)/2).
The index of the largest number in row n is A383846(n), corresponding to the index of the freed person in the corresponding Josephus problem.

			Consider a deck of four cards arranged in the order 1,2,4,3. In round 1, card 1 is dealt, card 2 is dealt, and card 4 goes under. Now the deck is ordered 3,4. In round 2, card 3 is dealt, then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,2,4,3.
The table begins:
  1;
  1, 2;
  1, 2, 3;
  1, 2, 4, 3;
  1, 2, 5, 3, 4;
  1, 2, 5, 3, 4, 6;
  1, 2, 6, 3, 4, 7, 5;
  1, 2, 8, 3, 4, 7, 5, 6;

Cf. A006257, A001651, A225381, A321298, A378635, A383845, A383846, A381050, A382528.

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        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.index(j)+1 for j in list(range(1, n+1))]
print([e for n in range(1, 14) for e in row(n)])

T(n,3j+1) = 2j+1, for 3j+1 <= n. T(n,3j+2) = 2j+2, for 3j+2 <= n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A378674 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and down-under dealing is used, then the resulting cards are put down in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A383076 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-skip-eliminate.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A383847 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 down-down-under dealing is used, then the resulting cards will be dealt in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula