cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

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

Original entry on oeis.org

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

Views

Author

Tanya Khovanova and the MIT PRIMES STEP junior group, Jan 15 2025

Keywords

Comments

Under-under-down dealing is a dealing pattern where the top card is placed at the bottom of the deck, then the next card is also 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 is related to a variation on the Josephus problem, where two people are skipped, and the third person is 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 A381667 is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is 3n.
The first column is A381591, the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A054995(n), corresponding to the index of the freed person in the corresponding Josephus problem.
T(n,3j) = j, for 3j <= n.

Examples

			Consider a deck of four cards arranged in the order 4,2,1,3. Card 4 goes under, card 2 goes under, and card 1 is dealt. Now the deck is ordered 3,4,2. Card 3 goes under, card 4 goes under, and card 2 is dealt. Now the leftover deck is ordered 3,4. Card 3 goes under, card 4 goes 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 4,2,1,3.
Table begins:
  1 ;
  1, 2;
  2, 3, 1;
  4, 2, 1, 3;
  2, 4, 1, 5, 3;
  6, 4, 1, 3, 5, 2;
  6, 3, 1, 7, 5, 2, 4;
  3, 5, 1, 7, 4, 2, 8, 6;
  9, 7, 1, 4, 6, 2, 8, 5, 3;

Crossrefs

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

Programs

  • Python
    def UUD(n):
    return invPerm(UUDES(n))
def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        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
sequence = []
for i in range(1,20):
    sequence += [str(v) for v in UUD(i)]
print(", ".join(sequence))
  • Python
    def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 0:
        i = (i + 2)%len(J)
        out.append(J.pop(i))
    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

Formula

T(n, 3 mod n) = 1
T(n, k) = T(n-1, k-3 mod n) + 1 if k != 3 mod n, where "a mod b" denotes the representative of the a's modular equivalence class in {0, ..., b-1}.

A381667 Triangle read by row: T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people where two people are skipped each step.

Original entry on oeis.org

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

Views

Author

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

Keywords

Comments

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 skips two numbers and the next number is eliminated. 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.
This variation of the Josephus problem is related to under-under-down card dealing, where the cards of a deck are dealt by alternately cycling two 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-down dealing if the deck begins in order 1,2,3,...,n.

Examples

			Consider 4 people in a circle. Initially, people numbered 1 and 2 are skipped, and person 3 is eliminated. The remaining people are now in order 4, 1, 2. Then 4 and 1 are skipped, and person 2 is eliminated. The remaining people are in order 4, 1. Now, 4 and 1 are skipped, and 4 is eliminated. Person 1 is eliminated last. Thus, the fourth row of the triangle is 3, 2, 4, 1.
Triangle begins;
  1;
  1, 2;
  3, 1, 2;
  3, 2, 4, 1;
  3, 1, 5, 2, 4;
  3, 6, 4, 2, 5, 1;
  3, 6, 2, 7, 5, 1, 4;
  3, 6, 1, 5, 2, 8, 4, 7;

Crossrefs

Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.

Programs

  • Python
    def UUDES(n):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=2
        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
sequence = []
for i in range(1,20):
    sequence += [str(v) for v in UUDES(i)]
print(", ".join(sequence))
  • Python
    def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 0:
        i = (i + 2)%len(J)
        out.append(J.pop(i))
    return out
print([e for n in range(1, 14) for e in row(n)]) # Michael S. Branicky, Mar 24 2025
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.