A321298 Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the Josephus elimination process for n people and a count of 2, 1 <= k <= n.

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

Offset

1,2

Comments

In the Josephus elimination process for n and k, the numbers 1 through n are written in a circle. A pointer starts at position 1. Each turn, the pointer skips (k-1) non-eliminated number(s) going around the circle and eliminates the k-th number, until no numbers remain. This sequence represents the triangle J(n, i), where n is the number of people in the circle, i is the turn number, and k is fixed at 2 (every other number is eliminated).

Links

Table of n, a(n) for n=1..98.

Index entries for sequences related to the Josephus Problem

Formula

From Pontus von Brömssen, Sep 18 2022: (Start)

The terms are uniquely determined by the following recursive formulas:

T(n,k) = 2*k if k <= n/2;

T(2*n,k) = 2*T(n,k-n)-1 if k > n;

T(2*n+1,k) = 2*T(n,k-n-1)+1 if k > n+1;

T(2*n+1,n+1) = 1.

(End)

Example

Triangle begins:
1;
2, 1;
2, 1, 3;
2, 4, 3, 1;
2, 4, 1, 5,  3;
2, 4, 6, 3,  1,  5;
2, 4, 6, 1,  5,  3, 7;
2, 4, 6, 8,  3,  7, 5, 1;
2, 4, 6, 8,  1,  5, 9, 7,  3;
2, 4, 6, 8, 10,  3, 7, 1,  9,  5;
2, 4, 6, 8, 10,  1, 5, 9,  3, 11, 7;
2, 4, 6, 8, 10, 12, 3, 7, 11,  5, 1, 9;
2, 4, 6, 8, 10, 12, 1, 5,  9, 13, 7, 3, 11;
...
For n = 5, to get the entries in 5th row from left to right, start with (^1, 2, 3, 4, 5) and the pointer at position 1, indicated by the caret. 1 is skipped and 2 is eliminated to get (1, ^3, 4, 5). (The pointer moves ahead to the next "live" number.) On the next turn, 3 is skipped and 4 is eliminated to get (1, 3, ^5). Then 1, 5, and 3 are eliminated in that order (going through (^3, 5) and (^3)). This gives row 5 of the triangle and entries a(11) through a(15) in this sequence.

Mathematica

Table[Rest@ Nest[Append[#1, {Delete[#2, #3 + 1], #2[[#3 + 1]], #3}] & @@ {#, #[[-1, 1]], Mod[#[[-1, -1]] + 1, Length@ #[[-1, 1]]]} &, {{Range@ n, 0, 0}}, n][[All, 2]], {n, 14}] // Flatten (* Michael De Vlieger, Nov 13 2018 *)

Prog

(Python)
def A321298(n, k):
    if 2*k<=n: return 2*k
    n2, r=divmod(n, 2)
    if r==0: return 2*A321298(n2, k-n2)-1
    if k==n2+1: return 1
    return 2*A321298(n2, k-n2-1)+1 # Pontus von Brömssen, Sep 18 2022

Crossrefs

The right border of this triangle is A006257.

Cf. A032434, A054995, A181281.

Sequence in context: A145706 A139631 A029177 * A261554 A161229 A029176

Adjacent sequences: A321295 A321296 A321297 * A321299 A321300 A321301

Keyword

easy,nonn,tabl

Author

Zeph L. Turner, Nov 02 2018

Extensions

Name clarified by Pontus von Brömssen, Sep 18 2022

Status

approved