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,2

Comments

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

Trivial cases: T(m,k)=m for m<k. This holds for m=k because the k-th person is removed first and, except for k=2, also for m=k+1 because the last three people are removed first.

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

Links

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

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

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

Example

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

Prog

(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));

Crossrefs

Cf. A005428, A032434, A054995, A007495.

Sequence in context: A359803 A290650 A346874 * A089606 A140740 A091918

Adjacent sequences: A348530 A348531 A348532 * A348534 A348535 A348536

Keyword

nonn,tabl

Author

Gerhard Kirchner, Oct 21 2021

Status

approved