Josephus Problem
Can anyone please provide the intuition behind the recurrence relation.
Jn,k=((Jn−1,k+k−1)modn)+1 why k-1 is added to the recurence relation?
Understanding for base 0 case is simpler.
Observation:
J_{n, k} = final position when we start the process from index 0
J’{n, k} = final position when we start the process from index x
so J’{n, k} = (J_{n, k} + x) % n
Now J_{n, k} with starting point 0 is equivalent to J_{n - 1, k} with starting point k
which is equivalent to (J_{n - 1, k} + k) % n with starting point 0
Which explains the recurrence.