Josephus Problem - Recurrence - Revisited - Unrolled

I am restarting Concrete Mathematics (Graham, Knuth, Patashnik) due to a forced break due to a neurological problem called Anti-NMDA receptor encephalitis. I include this detail because it is a relatively newly discovered disease and misdiagnosis is common so, in a very small way, raising awareness.

Maths is my friend in the recovery process even though it is challenging. Perhaps because it is challenging.

This post goes over the recurrence only because I found that challenging. For some reason I find recursion harder than it should be 😅

Setting the Scene with Some ExamplesPermalink

While the concept of shooting each second remaining person sounds obvious I found it useful to step through it on pen and paper which I will attempt to reproduce here in text; really an animation is also useful to look at such as this one. I won’t show a diagram because all you see is the end result which is not so useful

$n = 1$ - Survivor is $1$ obviously because Josephus does not want to kill himself.
$n = 2$
- 1 shoots 2
- 1 survives
$n = 3$
- 1 shoots 2
- 3 shoots 1
- 3 survives
$n = 4$
- 1 shoots 2
- 3 shoots 4
- 1 shoots 3
- 1 survives
… and so on - see above linked video for a great explanation.

I was accidentally thinking the dead person was also shooting someone (😅) which meant I was messing up above. Here is a tabular form of the above as presented in the book:

\begin{array}{cc} n & 1 2 3 4 5 6 \\ J (n) & 1 1 3 1 3 5 \end{array}

I think the point the book is trying to make is that, at each go around, we are essentially at the same point as the round before except there are half as many people _and their numbers (aka “label” or “position”) have changed. Or, as Wikipedia puts it:

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.

The RecurrencePermalink

This refers heavily to this post by, the ever helpful, Brian M. Scott. I am only adding even more details for my addled brain to help it understand.

First the recurrences (for base case, odd, and even) which is the notational expression of the above sentences:

\begin{aligned} J (1) & = 1 \\ J (2 n) & = 2 J (n) - 1, for n \geq 1; \\ J (2 n + 1) & = 2 J (n) + 1, for n \geq 1; \end{aligned}

UnrollingPermalink

The post by Brian M. Scott shows the case for $n = 21$ but I found it useful to step through the small cases as well.

Formatting note: I am using a comma followed by some notes. The font for the \text{...} is not beautiful but serves the purpose.

n = 1Permalink

This is the base case so $J (1) = 1$

n = 2Permalink

\begin{aligned} J (2) & = J (1 \cdot 2), expand \\ = 2 J (1) - 1, recurse \\ = 2 \cdot 1 - 1 = 1, base case and finish \end{aligned}

n = 3Permalink

\begin{aligned} J (3) & = J (1 \cdot 2 + 1), expand \\ = 2 J (1) + 1, recurse \\ = 2 \cdot 1 + 1 = 1, base case and finish \end{aligned}

n = 4Permalink

\begin{aligned} J (4) & = J (2 \cdot 2), expand \\ = 2 J (2) - 1, recurse \\ = 2 J (1 \cdot 2) - 1, expand \\ = 2 (2 J (1) - 1) - 1, recurse \\ = 4 J (1) - 3, simplify \\ = 4 \cdot 1 - 3 = 1, base case and finish \end{aligned}

n = 5Permalink

\begin{aligned} J (5) & = J (2 \cdot 2 + 1), expand \\ = 2 J (2) + 1, recurse \\ = 2 J (1.2) + 1, expand \\ = 2 (2 J (1) - 1) + 1, recurse \\ = 4 J (1) - 2 + 1, simplify \\ = 4 \cdot 1 - 1 = 3, base case and finish \end{aligned}

n = 6Permalink

\begin{aligned} J (6) & = J (2 \cdot 3), expand \\ = 2 J (3) - 1, recurse \\ = 2 J (1 \cdot 3) - 1, expand \\ = 2 (2 J (1) + 1) - 1, recurse \\ = 2 (2 \cdot 1 + 1) - 1 = 4 + 2 - 1 = 5, base case and finish \end{aligned}

ConclusionPermalink

Doing this manual unrolling really helps understand the nature of the problem when expressed in math notation. We can see how powers of two play a role which is useful in the closed for solution(s).

Share on

X Facebook LinkedIn Bluesky

Friedrich "Fred" Clausen