Josephus problem

The problem is explicitly solved when every second person will be killed (every person kills the person on their left or right), i.e. ${\displaystyle k=2}$. (For the more general case ${\displaystyle k\neq 2}$, a solution is outlined below.) The solution is expressed recursively. Let ${\displaystyle f(n)}$ denote the position of the survivor when there are initially n people (and ${\displaystyle k=2}$). The first time around the circle, all of the even-numbered people die. The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it is as though there were no first time around the circle.

If the initial number of people was even, then the person in position x during the second time around the circle was originally in position ${\displaystyle 2x-1}$ (for every choice of x). Let ${\displaystyle n=2j}$. The person at ${\displaystyle f(j)}$ who will now survive was originally in position ${\displaystyle 2f(j)-1}$. This yields the recurrence

${\displaystyle f(2j)=2f(j)-1\;.}$

If the initial number of people was odd, then person 1 can be thought of as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc. In this case, the person in position x was originally in position ${\displaystyle 2x+1}$. This yields the recurrence

${\displaystyle f(2j+1)=2f(j)+1\;.}$

When the values are tabulated of n and ${\displaystyle f(n)}$ a pattern emerges (OEIS: A006257, also the leftmost column of blue numbers in the figure above):

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle f(n)}$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

This suggests that ${\displaystyle f(n)}$ is an increasing odd sequence that restarts with ${\displaystyle f(n)=1}$ whenever the index n is a power of 2. Therefore, if m and l is chosen so that ${\displaystyle n=2^{m}+l}$ and ${\displaystyle 0\leq l<2^{m}}$, then ${\displaystyle f(n)=2\cdot l+1}$. It is clear that values in the table satisfy this equation. Or it can be thought that after l people are dead there are only ${\displaystyle 2^{m}}$ people and it goes to the ${\displaystyle 2l+1}$th person. This person must be the survivor. So ${\displaystyle f(n)=2l+1}$. Below, a proof is given by induction.

Theorem: If ${\displaystyle n=2^{m}+l}$ and ${\displaystyle 0\leq l<2^{m}}$, then ${\displaystyle f(n)=2l+1}$.

Proof: The strong induction is used on n. The base case ${\displaystyle n=1}$ is true. The cases are considered separately when n is even and when n is odd.

If n is even, then choose ${\displaystyle l_{1}}$ and ${\displaystyle m_{1}}$ such that ${\displaystyle n/2=2^{m_{1}}+l_{1}}$ and ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$. Note that ${\displaystyle l_{1}=l/2}$. ${\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}$ is had where the second equality follows from the induction hypothesis.

If n is odd, then choose ${\displaystyle l_{1}}$ and ${\displaystyle m_{1}}$ such that ${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$ and ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$. Note that ${\displaystyle l_{1}=(l-1)/2}$. ${\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}$ is had where the second equality follows from the induction hypothesis. This completes the proof.

l can be solved to get an explicit expression for ${\displaystyle f(n)}$:

${\displaystyle f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1}$

The most elegant form of the answer involves the binary representation of size n: ${\displaystyle f(n)}$ can be obtained by a one-bit left cyclic shift of n itself. If n is represented in binary as ${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$, then the solution is given by ${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$. The proof of this follows from the representation of n as ${\displaystyle 2^{m}+l}$ or from the above expression for ${\displaystyle f(n)}$.

Implementation: If n denotes the number of people, the safe position is given by the function ${\displaystyle f(n)=2l+1}$, where ${\displaystyle n=2^{m}+l}$ and ${\displaystyle 0\leq l<2^{m}}$.

Now if the number is represented in binary format, the first bit denotes ${\displaystyle 2^{m}}$ and remaining bits will denote l. For example, when ${\displaystyle n=41}$, its binary representation is

n    = 1   0   1   0   0   1
2m   = 1   0   0   0   0   0
l    =     0   1   0   0   1

/**
 * @param n the number of people standing in the circle
 * @return the safe position who will survive the execution 
 *   f(N) = 2L + 1 where N =2^M + L and 0 <= L < 2^M
 */
public int getSafePosition(int n) {
	// find value of L for the equation
	int valueOfL = n - Integer.highestOneBit(n);
	return 2 * valueOfL  + 1;
}

The easiest way to find the safe position is by using bitwise operators. In this approach, shifting the most-significant set bit of n to the least significant bit will return the safe position.[11] Input must be a positive integer.

n    = 1   0   1   0   0   1
n    = 0   1   0   0   1   1

/**
 * @param n (41) the number of people standing in the circle
 * @return the safe position who will survive the execution 
 */
public int getSafePosition(int n) {
    return ~Integer.highestOneBit(n*2) & ((n<<1) | 1);
    //     ---------------------- ---  | ------------
    //     Get the first set bit   |   | Left Shift n and flipping the last bit
    //    and take its complement  |   |
    //                             |   |
    //                Multiply n by 2  |
    //                         Bitwise And to copy bits exists in both operands.
}

In 1997, Lorenz Halbeisen and Norbert Hungerbühler discovered a closed-form for the case ${\displaystyle k=3}$. They showed that there is a certain constant

${\displaystyle \alpha \approx 0.8111...}$

that can be computed to arbitrary precision. Given this constant, choose m to be the greatest integer such that ${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$ (this will be either ${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$ or ${\displaystyle m^{\prime }-1}$). Then, the final survivor is

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$ if is rounded up else ${\displaystyle 1)}$

for all ${\displaystyle n\geq 5}$.

As an example computation, Halbeisen and Hungerbühler give ${\displaystyle n=41,k=3}$ (which is actually the original formulation of Josephus' problem). They compute:

${\displaystyle m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10}$

${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$ and therefore ${\displaystyle m=9}$

${\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31}$ (note that this has been rounded down)

${\displaystyle f(n)=3(41-31)+1=31}$

This can be verified by looking at each successive pass on the numbers 1 through 41:

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38

2, 4, 11, 16, 22, 25, 31, 35

2, 4, 16, 22, 31, 35

4, 16, 31, 35

16, 31

31

Dynamic programming is used to solve this problem in the general case by performing the first step and then using the solution of the remaining problem. When the index starts from one, then the person at ${\displaystyle s}$ shifts from the first person is in position ${\displaystyle ((s-1){\bmod {n}})+1}$, where n is the total number of persons. Let ${\displaystyle f(n,k)}$ denote the position of the survivor. After the ${\displaystyle k}$-th person is killed, a circle of ${\displaystyle n-1}$ remains, and the next count is started with the person whose number in the original problem was ${\displaystyle (k{\bmod {n}})+1}$. The position of the survivor in the remaining circle would be ${\displaystyle f(n-1,k)}$ if counting is started at ${\displaystyle 1}$; shifting this to account for the fact that the starting point is ${\displaystyle (k{\bmod {n}})+1}$ yields the recurrence[12]

${\displaystyle f(n,k)=((f(n-1,k)+k-1){\bmod {n}})+1,{\text{ with }}f(1,k)=1\,,}$

which takes the simpler form

${\displaystyle g(n,k)=(g(n-1,k)+k){\bmod {n}},{\text{ with }}g(1,k)=0}$

if the positions are numbered from ${\displaystyle 0}$ to ${\displaystyle n-1}$ instead.

This approach has running time ${\displaystyle O(n)}$, but for small ${\displaystyle k}$ and large ${\displaystyle n}$ there is another approach. The second approach also uses dynamic programming but has running time ${\displaystyle O(k\log n)}$. It is based on considering killing k-th, 2k-th, ..., ${\displaystyle (\lfloor n/k\rfloor k)}$-th people as one step, then changing the numbering.

This improved approach takes the form

${\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\{\begin{Bmatrix}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}}+n&{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)<n{\bmod {k}}\\\lfloor {\frac {k(g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}})}{k-1}}\rfloor &{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n\\\end{cases}}}$