A381049 -id:A381049 - cp's OEIS frontend

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

1, 1, 1, 4, 4, 1, 7, 4, 1, 7, 4, 10, 7, 13, 10, 16, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 28, 16, 31, 19, 34, 22, 37, 25, 40, 28, 43, 31, 46, 34, 49, 37, 52, 40, 1, 43, 4, 46, 7, 49, 10, 52, 13, 55, 16, 58, 19, 61, 22, 64, 25, 67

Offset: 1

Robert W. Vallin, Aug 18 2020

nonn

This variation of the Josephus problem is related to under-down-down card dealing. - Tanya Khovanova, Apr 14 2025

			Consider 4 people in a circle in order 1,2,3,4. In the first round, person 1 is skipped and persons 2 and 3 are eliminated. Now people are in order 4,1. In the second round, person 4 is skipped and person 1 is eliminated. Person 4 is freed. Thus, a(4) = 4. - _Tanya Khovanova_, Apr 14 2025

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Index entries for sequences related to the Josephus Problem

Cf. A006257, A225381, A321298, A378635, A381048, A381049, A382528.

nxt[{n_,a_,b_}]:={n+1,b,If[Mod[a+3,n+1]!=0,Mod[a+3,n+1],n+1]}; NestList[nxt,{2,1,1},70][[;;,2]] (* Harvey P. Dale, Jul 27 2024 *)

a(n) = if (n <= 2, 1, my(x = (a(n-2) + 3) % n); if (x, x, n)); \\ Michel Marcus, Aug 20 2020

a(n) = if (n<=1, return(1)); my(v=vector(n, i, i), w); while (#v > 3, if (#v <=3, w = [], w = vector(#v-3, k, v[k+3])); w = concat(w, Vec(v, 1)); v = w;); v[1]; \\ Michel Marcus, Mar 25 2025

a(1) = 1, a(2) = 1, a(n) = (a(n-2) + 3) (mod n) if (a(n-2) + 3) (mod n) is not 0; a(n) = n if (a(n-2) + 3) (mod n)=0.

Any number n can be written as either 2*(3^k) + 2m (where 0 <= m < 3^k, k = 0,1,2,...) or 3^k + 2m (where 0 <= m < 3^k, k = 0,1,2,...), in either case a(n) = 3m + 1.

More terms from Michel Marcus, Aug 20 2020

Title corrected by Tanya Khovanova, Apr 14 2025

A381048 Elimination order of the first person in a variation of the Josephus problem, where there are n people total. During each round the first person is skipped, and the second and the third person are eliminated. Then the process repeats.

Original entry on oeis.org

1, 2, 3, 3, 4, 6, 5, 6, 9, 7, 8, 11, 9, 10, 14, 11, 12, 18, 13, 14, 19, 15, 16, 22, 17, 18, 27, 19, 20, 27, 21, 22, 30, 23, 24, 35, 25, 26, 35, 27, 28, 38, 29, 30, 44, 31, 32, 43, 33, 34, 46, 35, 36, 54, 37, 38, 51, 39, 40, 54, 41, 42, 61, 43, 44, 59, 45, 46, 62, 47

Offset: 1

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

nonn

This elimination process is related to the under-down-down card dealing.

			Consider four people in order 1,2,3,4. In the first round, the first person is skipped and the second and the third persons are eliminated. Now people are ordered 4,1. In the second round, person 4 is skipped, and person 1 is eliminated. Thus, person 1 is eliminated third and a(4) = 3.

Cf. A006257, A007494, A225381, A321298, A378635, A337191, A381049, A382528.

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

a(3k+1) = 2k+1; a(3k-1) = 2k.

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

Original entry on oeis.org

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

Offset: 1

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

Under-down-down dealing is a dealing pattern where the top card is placed at the bottom of the deck, then the next two cards are dealt. This pattern repeats until all of the cards have been dealt.
This card dealing is related to a variation on the Josephus problem, where one person is skipped, and the next two are eliminated. 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 ??? is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is A007494(n) = ceiling(3n/2).
The first column is A381048, the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A337191(n), corresponding to the index of the freed person in the corresponding Josephus problem.

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

Cf. A006257, A007494, A225381, A321298, A378635, A337191, A381048, A381049.

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 DDU(n):
    return [0] + [(i)%2 for i in range(n)]
def DUD(n):
    return DDU(n+1)[1:]
def UDD(n):
    return DUD(n+1)[1:]
seq = []
for i in range(1,10):
    seq += T(i, UDD(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 + 1)%len(J)
        out.append(J.pop(i))
        i = i%len(J)
        if len(J) > 1:
            out.append(J.pop(i))
    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, Apr 28 2025

T(n,k) = T(n-2,k-3) + 2. T(1,1) = 1. For the first 3 columns, we have T(n,1) = T(n-2,n-2) + 2, T(n,2) = 1, and T(n,3) = 2.

It follows that T(n,3k+2) = 2k+1, T(n,3k) = 2k.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A381048 Elimination order of the first person in a variation of the Josephus problem, where there are n people total. During each round the first person is skipped, and the second and the third person are eliminated. Then the process repeats.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Python

Formula