You are one of 1000 captured pirates about to be tied to posts numbered 1 to 1000 arranged in a circle.

The general answer [Editor: the original begins "Well, The general
answer"] for N posts skipping by 2 is:

  (<number of posts> - <largest power of 2 less than posts>)*2

For 1000 that would be (1000-512)*2 => 976.

Of course this assumes that:
They count up (i.e. they start at 1 then go to 3, not 999),
That a dead pirate is not counted when they come around the second time,
That the numbers are arranged in order,
And that you would rather live after watching 999 of your friends
executed in a horribly gruesome manner.

Question [Editor: lowercase "question" in the original]: What is the general solution for N posts skipping by S?

-- Scott Nelson (snelson@engr.sgi.com)

Well, for S=2...

If the second person is the first person killed, then the following
interesting feature shows: Write the original N in binary, move the
first 1 to the end of the binary representation, and the result is the
binary representation of the last person left.

For the problem as stated, just subtract one from the result.

Another question: If the last 2 will be set free, what 2 positions could
you choose?

-- Ken Duisenberg (duizie@isl.Stanford.EDU)

[ Editor: for N = 1000 = 1111101000 in binary, moving the leading 1 to
the end gives 1111010001 = 977, and 977 - 1 = 976, agreeing with the
formula above.  This is the classical Josephus problem. ]

[ Editor: results of a 1996 rec.puzzles contest on the Josephus
problem, in the form where n people stand in a circle, every second one
is eliminated, and p(n) is the position of the survivor. ]

I thought the Josephus puzzle was somewhat obscure (I didn't find it in
the r.p archives, at least).  But since I posted this a week ago, I've
seen it referred to here, posted in panthera's contest, and rephrased
as the "Aliens have Landed" problem!

All answers I received were correct, but none included any
justification for their correctness.  (To be fair, I didn't explicitly
request any.)

Ed Murphy (zvyezda@ix.netcom.com) deduced the recurrence but did not
solve it in closed form:
        p(1) = 1
        p(2n) = 2p(n)-1
        p(2n+1) = 2p(n)+1

Several others, Pierre Grant (pgrant@total.net), C. Maverick Petersen
(bungee@3do.com), and Alex Yeilding (yeilding@ix.netcom.com) all gave
closed forms (and unfortunately Alex posted his to the net, but later
deleted it).

The closed form is 2L+1, where L=n-floor(log_2(n)).  The floor(x) is
the greatest integer less than or equal to x.

[ Editor: as written this disagrees with the recurrence: for n = 5 it
gives L = 5-2 = 3 and 2L+1 = 7, but p(5) = 2p(2)+1 = 3. ]

Finally, Matt Dickey (matt.dickey@SanDiegoCA.NCR.com), gave both a
closed form and the cute "computer literate" answer: Express n as a
binary number.  Rotate the bits one position to the left (with the high
order bit of n ending up as the low-order bit of the result).

For those interested in the Josephus problem as well as much harder
variants and unsolved questions related to Josephus sets, a good
starting point is "Concrete Mathematics" by Graham, Knuth, and
Patashnik.  (Many think this is the finest math text ever written.)

-- John Black, Jr. <blackj@toadflax.cs.ucdavis.edu>