login
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
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
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
KEYWORD
nonn,tabl
AUTHOR
Gerhard Kirchner, Oct 21 2021
STATUS
approved