OFFSET
1,3
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.
LINKS
Eric Huang, Tanya Khovanova, Timur Kilybayev, Ryan Li, Brandon Ni, Leone Seidel, Samarth Sharma, Nathan Sheffield, Vivek Varanasi, Alice Yin, Boya Yun, and William Zelevinsky, Card Dealing Math, arXiv:2509.11395 [math.NT], 2025. See p. 17.
EXAMPLE
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;
PROG
(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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 03 2025
STATUS
approved
