A384774 -id:A384774 - cp's OEIS frontend

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.

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

A384772 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 first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Original entry on oeis.org

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

Offset: 1

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

The numbers 1 through n are arranged in a circle. A pointer starts at position 1. With each turn, the pointer skips three numbers and the next number is eliminated. The process repeats until no numbers remain. This sequence is a concatenation of the rows of the triangle T, where T(n, k) is the elimination order of the k-th number in a circle of n numbers.

This variation of the Josephus problem can equivalently be described in terms of under-under-under-down card dealing, where the cards of a deck are dealt by alternately cycling three cards from the top "under", and then dealing the next card "down". In particular, T(n,k) is the k-th card dealt in under-under-under-down dealing if the deck begins in order 1,2,3,...,n.

			Consider 4 people in a circle. Initially, people numbered 1, 2, and 3 are skipped, and person 4 is eliminated. The remaining people are now in order 1, 2, 3. Then all three are skipped and person 1 is eliminated. The remaining people are in order 2, 3. Now, we skip over 2, 3, 2 and eliminate person 3. Person 2 is eliminated last. Thus, the fourth row of the triangle is 4, 1, 3, 2.
The triangle begins as follows:
  1;
  2, 1;
  1, 3, 2;
  4, 1, 3, 2;
  4, 3, 5, 2, 1;
  4, 2, 1, 3, 6, 5;
  4, 1, 6, 5, 7, 3, 2;
  4, 8, 5, 2, 1, 3, 7, 6;
  4, 8, 3, 9, 6, 5, 7, 2, 1

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

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

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

A384772 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 first three people are skipped, then one is eliminated, repeating until all n people are eliminated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

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