3

On page 25 of the second edition I am at the section revisiting the initial guess of a closed form solution for the Josephus Problem. This initial, and incorrect, guess was that the solution is $n/2$. To lead us into this renewed discussion the book says:

Let's return briefly to our first guess, that $J(n) = n/2$ when $n$ is even. This is obviously not true in general, but we can now determine exactly when it is true

To find when this is true they substitute in the closed form solution and $2^m +l$ for the $n$ it represents. Then rearrange to find $l$ i.e.

$$J(n)=n/2$$ $$2l+1=(2^m+l)/2$$ $$l=\frac{(2^m-2)}{3}$$

If the number $l=\frac{(2^m-2)}{3}$ is an integer then $n=2^m+l$ will be a solution because $l$ will be less than $2^m$

This implies, by my reading, that $l$ is sometimes greater than $2^m$. Isn't $l$ always less than $2^m$? If $l$ were greater than $2^m$ then we would be going to the next power of two "block"? (As described on page 23 in the table of small values given by the recurrence)

Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12

1 Answers1

1

You are correct that $l$ was originally defined as the remainder after removing the most significant bit $2^m$ from the number $n$, hence originally $l<2^m$.

BUT at this point the claim is that the formula: $$ l:=\frac{2^m-2}3\tag{$\varphi$} $$ will produce numbers of the form $n=2^m+l$ that solve $J(n)=n/2$. So here $l$ is no longer defined as the remainder, but from formula $(\varphi)$ given above. Hence we need to note that it works correctly for it to have any relevance to the problem ie. it can be used to build a number $n=2^m+l$ having $2^m$ as its most significant bit and $l$ as its remainder.

Suppose formula $(\varphi)$ above could produce $l>2^m$. Then what would we have achieved in relation to the actual problem? Then $2^m$ would NOT be $n$'s most significant bit and $l$ would NOT be the relevant remainder used in the Josephus formula.

I hope this is clear and helps!

String
  • 18,395