2
$\begingroup$

This question was asked about a group of people whom a king wishes to play a cruel game with. Going around in a circle, the king kills every other person.

The question concerned how one could compute the answer without executing the sequence, and this answer comes out to $n=2^m+p$, where $n$ is the number of people, $2^m$ is the highest value less than $n$, and $p$ is the seat number of the person who lives.

What happens if the king kills every third person? Fourth person? For convenience, let $s$ be the number of seats skipped.

I've worked out the first few digits in the sequence where $s=3$, as $1, 2, 2, 1, 4, 1, 4, 7$, but I don't see a pattern here. I imagine I'd have to generate quite a number of these to see the pattern. The first few digits where $s=4$ are $1, 2, 3, 2, 1, 5, 2, 6, 1$.

How does one generate this sequence in a generic way for any $s$?

$\endgroup$
4
$\begingroup$

As mentioned in the previous thread, this is the (generalized) Josephus problem, known as such because the oldest known reference (at least in Western history) is by the historian Flavius Josephus.

There is no known general closed form. You can compute the position of the survivor by recurrence: $$p_s^n = \begin{cases} 1 + (p^{n-1}_s - 1 + s) \bmod n & \text{if \(n \gt 1\)} \\ 1 & \text{if \(n = 1\)} \\ \end{cases}$$ where $p_s^n$ is position of the survivor for the $s$-step Josephus problem with $n$ people.

The Online Encyclopedia of Integer Sequences should always be your first hit when you have a sequence of integers. It has a bunch of entries tagged “Josephus”, including

  • A006257: survivor for $s=2$
  • A054995: survivor for $s=3$
  • A088333: survivor for $s=4$
  • A181281: survivor for $s=5$
  • A032434: $p_s^n+1$ for $s \le n$, in lexicographic order of $(s,n)$

The reference for A054995 gives a formula for $s=3$: $$p^3_n = 3n+1 - \lfloor K(3) \cdot (3/2)^{\lceil L(3) \rceil} \rfloor$$ where $ L(3) = \dfrac{\log((2n+1)/K(3))}{\log(3/2)} $ and $K(3) \approx 1.62227050288476731595695$ as seen in A083286. See “Functional iteration and the Josephus problem” by A. M. Odlyzko and H. S. Wilf for a proof and generalization. There is also a proof with didactic commentary in Concrete Mathematics (Graham, Knuth and Patashnik, 1994 (2nd ed.)) §3.3. Note that this doesn't really help to compute the values, because computing a precise enough value of $K(3)$ is as hard as computing $p^3_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.