cp's OEIS Frontend

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.

%I A348533 #22 Dec 13 2021 16:06:55
%S A348533 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,
%T A348533 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,
%U A348533 7,6,5,4,3,2,1,2048,70,22,12,8,7,6,5,4,3,2,1
%N 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.
%C A348533 The table, see example, is read by ascending antidiagonals.
%C A348533 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.
%C A348533 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.
%C A348533 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).
%C A348533 T(m,2) =  A000079(m)=2^(m-1)
%C A348533 T(m,3) -> A073941
%C A348533 T(m,4) -> A072493
%C A348533 T(m+4,4)= A005427(m)
%C A348533 T(m,5) -> A120160
%C A348533 T(m,6) -> A120170
%C A348533 T(m,7) -> A120178
%C A348533 T(m,8) -> A120186
%C A348533 T(m,9) -> A120194
%C A348533 T(m,10)-> A120202
%H A348533 Gerhard Kirchner, <a href="/A348533/a348533.pdf">Derivation of the recurrence </a>
%H A348533 Gerhard Kirchner, <a href="/A348533/a348533.txt">Table for 2<=k<=10 and 1<=m<=30</a>
%H A348533 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F A348533 Recurrence for T(m,k) and S(m,k), the survivor's number.
%F A348533 Start: T(1,k)=S(1,k)=1.
%F A348533 T(m+1,k)=(k*T(m,k)+e)/(k-1),
%F A348533 S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),
%F A348533 with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).
%e A348533 k=4: 7 people, survivors number 2 <4.
%e A348533 k=4: 6 people, survivors number 5>=4, counterexample.
%e A348533 Table T(m,k) begins:
%e A348533   m\k____2____3____4____5
%e A348533    1:    1    1    1    1
%e A348533    2:    2    2    2    2
%e A348533    3:    4    3    3    3
%e A348533    4:    8    4    4    4
%e A348533    5:   16    6    5    5
%e A348533    6:   32    9    7    6
%e A348533    7:   64   14    9    8
%e A348533    8:  128   21   12   10
%e A348533    9:  256   31   16   12
%e A348533   10:  512   47   22   15
%o A348533 (Maxima)
%o A348533 block(k:10, mmax:30, t:1, s:1, T:[1],
%o A348533 /*Terms T(m,k), m=1 thru mmax */
%o A348533 for m from 1 thru mmax-1 do(
%o A348533     p:  mod(t, k-1),
%o A348533     if s>p then e:-p else e:k-1-p,
%o A348533     t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
%o A348533     T:append(T,[t])),
%o A348533 return (T));
%Y A348533 Cf. A005428, A032434, A054995, A007495.
%K A348533 nonn,tabl
%O A348533 1,2
%A A348533 _Gerhard Kirchner_, Oct 21 2021