### Solution to June’s Puzzle: Josephus Problem

The Josephus problem is an ancient puzzle that involves a group of 41 men standing in a circle. Going around the circle, every second standing man is executed (one skipped, one executed) until only one man is left standing. Assuming that the positions are numbered 1 through 41, which position should Josephus (one of the men) choose if he could, so that he would be the only one to remain standing? Can you generalize the solution for n men? Write a T-SQL solution that returns the position based on the input number of men @n.

An easy way to find a generic solution to this
puzzle with any number of men is to first solve it
with very small numbers of men (1, 2, 3, and so on),
and to look for a pattern in the results. If you solve
the puzzle for small numbers, you get the results
shown in Web Table A (www.sqlmag.com, InstantDoc
ID 99039), where *n* is the number of men, and p is
the position of the only man left.

The pattern you can identify is that p is an increasing
sequence of odd integers that restarts from 1
when *n* is a power of 2. You express n as 2^a + b,
where b >= 0 and b < 2^a. That is, a is the highest
power of 2 such that 2^a is smaller than n, and b is n
minus 2^a. Then, p can be expressed as 2b + 1. For
example, for n = 41, you express n as 2^5 + 9. Since
b = 9 and p = 2b + 1, you get p = 19.

Of course, this is just an observation of a pattern based on the cases that were tested. To ensure that the pattern holds for all cases, you need a mathematical proof. You can find such a proof at en.wikipedia.org/wiki/Josephus_problem. The following T-SQL expression calculates p for a given @n:

DECLARE @n AS INT; SET @n = 41; SELECT 2 * (@n - POWER(2, CAST(LOG(@n)/LOG(2) AS INT))) + 1 AS p;