A054995 -id:A054995 - cp's OEIS frontend

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

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 22 2025

Down-under-under dealing is a dealing pattern where the top card is dealt; then the next two cards are 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 person is eliminated, then two people are skipped, and then the process is repeated. 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 A381623(n) is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is 3n-2.
The first column consists of all ones: it is the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A054995(n-1)+1, corresponding to the index of the freed person in the corresponding Josephus problem.
T(n,3j-2) = j, for 3j-2 <= n.

			Consider a deck of four cards arranged in the order 1,3,4,2. Card 1 is dealt. Then cards 3 and 4 go under, and card 2 is dealt. Now the deck is ordered 3,4. Cards 3 and 4 go under, and card 3 is dealt. Then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,3,4,2.
Table begins:
1;
1, 2;
1, 2, 3;
1, 3, 4, 2;
1, 5, 3, 2, 4;
1, 3, 5, 2, 6, 4;
1, 7, 5, 2, 4, 6, 3;
1, 7, 4, 2, 8, 6, 3, 5;

Cf. A006257, A016777, A054995, A225381, A321298, A378635, A381623.

def T(n, A):
    return invPerm(J(n,A))
def J(n,A):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=A[i]
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
def DUU(n):
    return [0] + [2 for i in range(n)]
seq = []
for i in range(1,20):
    seq += T(i, DUU(i))
print(", ".join([str(v) for v in seq]))

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 + 2)%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)]) # Michael S. Branicky, Mar 27 2025

For any n, we have T(n,1) = 1. T(2,2) = 2. For n > 2, T(n,2) = T(n-1,n-2) + 1 and T(n,3) = T(n-1,n-1) + 1. For n > 3 and k > 3, T(n,k) = T(n-1,k-3) + 1.

A381623 Triangle read by rows: 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 first person is eliminated, then two people are skipped, and then the process repeats.

Original entry on oeis.org

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

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 22 2025

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

Cf. A006257, A016777, A054995, A225381, A321298, A378635, A381622.

def J(n,A):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=A[i]
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
def DUU(n):
    return [0] + [2 for i in range(n)]
seq = []
for i in range(1,20):
    seq += J(i, DUU(i))
print(", ".join([str(v) for v in seq]))

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 + 2)%len(J)
    return out + [J[0]]
print([e for n in range(1, 14) for e in row(n)]) # Michael S. Branicky, Mar 27 2025

A209258 The original Josephus problem: 41 soldiers are arranged in a ring, and every third man is killed by his neighbor, until only the last person remains, who would kill himself. Sequence shows soldier killing order.

Original entry on oeis.org

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16, 31

Offset: 1

Arkadiusz Wesolowski, Jan 14 2013

Josephus and another soldier did not agree with that proposal. By choosing positions 31 and 16 in the ring, Josephus and his companion saved their lives.

As a mathematics problem, the classic "Josephus problem" assumes that the soldiers arranged themselves in a circle and counted by threes to determine the order in which they would be killed, and the comment above assumes that Josephus and the one other survivor deliberately placed themselves in the two positions that would make them the last two survivors, but neither of these assumptions is supported by the account of Josephus himself (see the quote at the Links entry). - Jon E. Schoenfield, Jun 04 2017

Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus Problem

Cf. A054995.

Needs["Combinatorica`"]
InversePermutation@Josephus[41, 3]
lst = {}; r = 41; s = Range[r]; Do[s = RotateLeft[s, 2]; AppendTo[lst, First[s]]; s = Rest[s], {r}]; lst

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

Formula

A381623 Triangle read by rows: 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 first person is eliminated, then two people are skipped, and then the process repeats.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

A209258 The original Josephus problem: 41 soldiers are arranged in a ring, and every third man is killed by his neighbor, until only the last person remains, who would kill himself. Sequence shows soldier killing order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica