A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 4, 3, 2, 1, 32, 6, 4, 3, 2, 1, 64, 9, 5, 4, 3, 2, 1, 128, 14, 7, 5, 4, 3, 2, 1, 256, 21, 9, 6, 5, 4, 3, 2, 1, 512, 31, 12, 8, 6, 5, 4, 3, 2, 1, 1024, 47, 16, 10, 7, 6, 5, 4, 3, 2, 1, 2048, 70, 22, 12, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Author

Gerhard Kirchner, Oct 21 2021

Keywords

• nonn
• tabl

Comments

The table, see example, is read by ascending antidiagonals.

Trivial cases: T(m,k)=m for m

The recurrence in the formula section does not only yield T(m,k), but also the survivor's number S(m,k) so that the Josephus problem can be solved for any number N of people, especially for large N because T(m,k) grows exponentially, see link "Derivation of the recurrence", section II.

T(m,k) compared with other sequences ("->" means that the sequences can be made equal by removing repeated terms, see link "Derivation of the recurrence", section IV).

T(m,2) = A000079(m)=2^(m-1)

T(m,3) -> A073941

T(m,4) -> A072493

T(m+4,4)= A005427(m)

T(m,5) -> A120160

T(m,6) -> A120170

T(m,7) -> A120178

T(m,8) -> A120186

T(m,9) -> A120194

T(m,10)-> A120202

Examples

			k=4: 7 people, survivors number 2 <4.
k=4: 6 people, survivors number 5>=4, counterexample.
Table T(m,k) begins:
  m\k____2____3____4____5
   1:    1    1    1    1
   2:    2    2    2    2
   3:    4    3    3    3
   4:    8    4    4    4
   5:   16    6    5    5
   6:   32    9    7    6
   7:   64   14    9    8
   8:  128   21   12   10
   9:  256   31   16   12
  10:  512   47   22   15
		

Links

• Gerhard Kirchner, Derivation of the recurrence
• Gerhard Kirchner, Table for 2<=k<=10 and 1<=m<=30
• Index entries for sequences related to the Josephus Problem

Crossrefs

Cf. A005428, A032434, A054995, A007495.

Programs

Maxima

block(k:10, mmax:30, t:1, s:1, T:[1],
/*Terms T(m,k), m=1 thru mmax */
for m from 1 thru mmax-1 do(
    p:  mod(t, k-1),
    if s>p then e:-p else e:k-1-p,
    t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
    T:append(T,[t])),
return (T));

Formula

Recurrence for T(m,k) and S(m,k), the survivor's number.

Start: T(1,k)=S(1,k)=1.

T(m+1,k)=(k*T(m,k)+e)/(k-1),

S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),

with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).

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

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