A384772 -id:A384772 - cp's OEIS frontend

A384774 Elimination order of the first person in a variation 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, 2, 5, 3, 2, 5, 9, 8, 3, 12, 6, 10, 4, 16, 12, 16, 5, 9, 20, 10, 6, 22, 21, 23, 7, 27, 13, 21, 8, 30, 23, 20, 9, 16, 31, 17, 10, 31, 24, 35, 11, 34, 20, 27, 12, 28, 34, 49, 13, 23, 31, 24, 14, 49, 55, 34, 15, 35, 27, 59, 16, 44, 38, 60, 17, 30, 53, 31

Offset: 1

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

nonn

a(4k-1) = k

a(n) = A384770(n,1).

			Consider n = 4 people. The first person eliminated is number 4. This leaves the remaining people in order 1, 2, 3. On the second step, we eliminate person number 1, implying that the order of elimination of the first person is 2: a(4) = 2.

Cf. First column of A384770.

Cf. A225381, A384772, A088333.

A384774 := proc(n::integer)
    local plist,eli,skip,ptr ;
    plist := [seq(i,i=1..n)] ;
    eli :=1 ;
    skip := 3;
    ptr := 0 ;
    while true do
        ptr := modp(ptr+skip,nops(plist)) ;
        if op(ptr+1,plist) = 1 then
            return eli ;
        end if;
        plist := subsop(ptr+1=NULL,plist) ;
        eli := eli+1 ;
    end do:
end proc:
seq(A384774(n),n=1..100) ; # R. J. Mathar, Jul 30 2025

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

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

Original entry on oeis.org

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

Offset: 1

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

Under-under-under-down dealing is a dealing pattern where the top three cards are placed at the bottom of the deck, and then the next card is dealt. 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 every 4th person is eliminated. T(n,k) is the number of eliminations in the Josephus problem that occur before the k-th person is eliminated. Equivalently, each row of T is the inverse permutation of the corresponding row of the Josephus triangle A384772, i.e. A384772(n,T(n,k)) = k.
The total number of moves for row n is 4n.
The first column is A384774(n), the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A088333(n), corresponding to the index of the freed person in the corresponding Josephus problem.
T(n,4j) = j, for 4j <= n.

			Consider a deck of four cards arranged in the order 2,4,3,1. If we put the top 3 cards under and deal the next card, we will deal card number 1. Now the deck is ordered 2,4,3. If we place 3 cards under and deal the next one, we will deal card number 2, and be left with cards 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,4,3,1.
The triangle begins as follows:
 1
 2, 1;
 1, 3, 2;
 2, 4, 3, 1;
 5, 4, 2, 1, 3;
 3, 2, 4, 1, 6, 5;
 2, 7, 6, 1, 4, 3, 5;
 5, 4, 6, 1, 3, 8, 7, 2;
 9, 8, 3, 1, 6, 5, 7, 2, 4

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

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = (i + 3)%len(J)
        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)])

T(n, 4) = 1 for n >= 4

T(n, k) = T(n-1, k-4 mod n) + 1 if k !== 4 (mod n).

A385327 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the first person is the last to be eliminated.

Original entry on oeis.org

1, 2, 5, 9, 12, 16, 218, 517, 1226, 6890, 12249, 16332, 21776, 38713, 122353, 687461, 1222153, 51443354, 385389994, 1218022698, 1624030264, 2887164914, 5132737625, 9124866889, 28839085477, 162036891790, 910429504490, 2877406829006, 5115389918233, 510385736583765

Offset: 1

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

nonn

This sequence can be used in magic tricks with under-under-under-down dealing pattern. The deck sizes in this sequence guarantee that after the dealing, the last dealt card is the one that was initially on top.
The classical Josephus problem corresponds to under-down dealing. In this case, the first person is freed when the number of people is a power of 2: A000079.
If two people are skipped, then the corresponding sequence is A081614.

			Suppose there are 5 people in a circle. After three people are skipped, the person number 4 is eliminated. The leftover people are 5,1,2,3 in order. Then person number 3 eliminated, and the leftover people are 5,1,2 in order. Then person number 5 is eliminated, and the leftover people are 1,2 in order. Then person number 2 is eliminated, and person 1 is freed. Thus, 5 is in this sequence.

Cf. A000079, A081614, A088333, A384770, A384772, A384774, A385333.

def freed_person_sequence_periodic(trailingUs, periodic_portion, numterms):
    freed_person_table=[[0] for i in periodic_portion]
    for i in range(numterms):
        extend_freed_person_sequence(periodic_portion, freed_person_table)
    return [(freed_person_table[0][N] - trailingUs)%(N+1)+1 for N in range(len(freed_person_table[0]))]
def extend_freed_person_sequence(periodic_portion, freed_person_table):
    for offset in range(len(periodic_portion)):
        first_death = periodic_portion[offset]
        remaining_survivor = freed_person_table[(offset + 1)%len(periodic_portion)][len(freed_person_table[offset])-1]
        if remaining_survivor + first_death + 1 < len(freed_person_table[offset])+ 1:
            freed_person_table[offset].append(remaining_survivor + first_death + 1)
        else:
            freed_person_table[offset].append((remaining_survivor + first_death + 1) % (len(freed_person_table[offset]) + 1))
def first_freers_periodic(trailingUs, periodic_portion, numterms):
    freed_seq = freed_person_sequence_periodic(trailingUs, periodic_portion, numterms)
    return [i+1 for i in range(len(freed_seq)) if freed_seq[i] == 1]
print(first_freers_periodic(0, [3], 100000000))

More terms from Jinyuan Wang, Jul 01 2025

A385333 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the last person is the last to be eliminated.

Original entry on oeis.org

1, 21, 38, 51, 122, 163, 689, 919, 2906, 3875, 5167, 51617, 68823, 163137, 290022, 1629537, 6866858, 9155811, 16276998, 28936886, 38582515, 121939802, 162586403, 216781871, 289042495, 513853325, 685137767, 913517023, 2165373685, 12166489185, 38452113969, 121527668842

Offset: 1

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

nonn

This sequence can be used in magic tricks with under-under-under-down dealing pattern. The deck sizes in this sequence guarantee that after the dealing, the last card dealt is the one that was initially on the bottom.

			Suppose there are 5 people in a circle. After three people are skipped, the person number 4 is eliminated. The leftover people are 5,1,2,3 in order. Then person number 3 eliminated, and the leftover people are 5,1,2 in order. Then person number 5 is eliminated, and the leftover people are 1,2 in order. Then person number 2 is eliminated, and person 1 is freed. Thus, 5 is NOT in this sequence.

Cf. A088333, A384770, A384772, A384774, A385327.

Cf. A000225 (for skip 1 take 1), A182459 (for skip 2 take 1).

More terms from Jinyuan Wang, Jul 01 2025

cp's OEIS Frontend

A384774 Elimination order of the first person in a variation of the Josephus problem in which first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A385327 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the first person is the last to be eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Extensions

A385333 The numbers of people such that, in the variant of the Josephus problem in which three people are skipped and then one is eliminated, the last person is the last to be eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions