Josephus survivor

n people stand in a circle numbered 1..n. Starting from person 1 and counting, every k-th person is eliminated; counting resumes from the next person. Return the 1-indexed position of the last survivor (the Josephus problem). Use the O(n) recurrence, not a simulation. Constraints: 1 <= n <= 100000, 1 <= k <= 10^9.