: An interesting fact about : The Josephus Problem in : Introduction and an example.

Recursive relations and some formulas for JI(n).

Theorem 2.1 (1)   $JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor$.
(2) $JI(8n+1) = 8n+5-4JI(2n).$
(3) $JI(8n+2) = 4JI(2n)-3- \lfloor JI(2 n)/(n + 2) \rfloor$.
(4) $JI(8n+3) = 8n+7-4JI(2n).$
(5) $JI(8n+4) = 8n+8-4JI(2n+1)+ \lfloor JI(2n+1)/(n+2) \rfloor.$
(6) $JI(8n+5) = 4JI(2n+1)-1.$
(7) $JI(8n+6) = 8n+10-4JI(2n+1)+ \lfloor(JI(2n+1)/(n+2)\rfloor.$
(8) $JI(8n+7) = 4JI(2n+1)-3,$
where $\lfloor \ \rfloor$ is the floor function.

Proof (1)   We suppose that there are $8n$ numbers. The first process begins to eliminate them, starting with the 2nd number, while the second process starts with the $(8n-1)$-th number. When the two processes have eliminated $4n$ numbers, $4n$ numbers remain. See Figure 2.1.
After this, the two processes are going to intersect each other.
When $6n$ numbers are eliminated, $2n$ numbers remain. See Figure 2.2.
Here the number with an underline was eliminated for the last time, and the number with a double underline was eliminated just before it.
Since there are $2n$ numbers remaining, $JI(8n)$ depends on $JI(2n).$
If $JI(2n) = 1, 2, ...,n$, then by Figure 2.2 we have $JI(8n) = 3, 7, ..., 4n-1$.
Therefore If $JI(2n) \leq n$, then
$JI(8n) = 4JI(2n) - 1$.
If $JI(2n) = n+1, ...,2n$, then by Figure 2.2 $JI(8n) = 4n+2, ...,8n-2$.
Therefore if $JI(2n) \geq n+1$, then
$JI(8n) = 4JI(2n) - 2$.
By using the floor function we can express these two equations of $JI(8n)$ by one equation $JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor$. We have proved (1) of Theorem 2.1.

Figure (2.1.) 　　　　　　　　　　　　　　Figure (2.2)
(2) We suppose that there are $8n+1$ numbers. When $6n+1$ numbers are eliminated, $2n$ numbers remain. See Figure 2.3.
Here the number with an underline was eliminated for the last time, and the number with a double underline was eliminated just before it.
Since $2n$ numbers remain, $JI(8n+1)$ depends $JI(2n).$
When we begin to eliminate $2n$ numbers that remain, the second process will eliminate $8n-3$, and after that the first process will eliminate 9.
Therefore we can assume that we have the Josephus problem with the list
{ 8n+1, 8n-3, ..., 9, 5 }, where the first number to be eliminated is $8n-3$, and the second number is $9$. Therefore if $JI(2n) = 1,2,...,2n$, then $JI(8n) = 8n+1, 8n-3,...,5$, and hence
$JI(8n+1) = 8n+5-4JI(2n)$.
We have proved (2) of Theorem 2.1.
(3) We suppose that there are $8n+2$ numbers. When 6n+2 numbers are eliminated, 2n numbers remain. See Figure 2.4. By the method that is similar to the one we used in (1) we can prove (3).

Figure (2.3.)　　　　　　　　　　　　　　　　 Figure (2.4)
(4) We suppose that there are $8n+3$ numbers. When $6n+3$ numbers are eliminated, $2n$ numbers remain. See Figure 2.5. By the method that is similar to the one we used in (2) we can prove (4).
(5) We suppose that there are $8n+4$ numbers. The situation of (5) is different from these of (1), (2), (3) and (4). When $6n+3$ numbers are eliminated, $2n+1$ numbers remain. When there are $2n+1$ numbers remain, there is not any number left between the number with an underline and the number with a double underline. See Figure 2.6. By the method that is similar to the one we used in (2) we can prove (5).

Figure (2.5.) 　　　　　　　　　　　　　Figure (2.6)
(6) We suppose that there are $8n+5$ numbers. When $6n+4$ numbers are eliminated, $2n+1$ numbers remain. See Figure 2.7. Similarly we can prove (6).
(7) We suppose that there are $8n+6$ numbers. When $6n+5$ numbers are eliminated, 2n+1 numbers remain. See Figure 2.8. Similarly we can prove (7).

Figure (2.7.) 　　　　　　　　　　　　　　　　　Figure (2.8)
(8) We suppose that there are $8n+7$ numbers. When $6n+6$ numbers are eliminated, $2n+1$ numbers remain. See Figure 2.9. Similarly we can prove (8).
Figure (2.9.)

Lemma 2.1   $J(2n) \neq n + 1$ for any natural number $n$.

Proof   By Theorem 2.1 we have $JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor$,
and hence $JI(8n) = 3, ..., 4n-1, 4n+2, ...$ for $JI(2n)= 1, ...,n, n+1, ...$. Clearly we have $J(8n) \neq 4n + 1.$
Similarly we can prove that
$J(8n+2) \neq 4n + 2$, $J(8n+4) \neq 4n + 3$ and $J(8n+6) \neq 4n + 4$.

: An interesting fact about : The Josephus Problem in : Introduction and an example.