Josephus Problem

Date: 04/18/2003 at 20:39:50
From: Jeremy
Subject: Determining an equation from a series

There are x people sitting around a table. Every other person at the 
table is eliminated until there is only one person left. For 
instance, at a four-person table, the second and fourth person are 
eliminated; then going around the table once more, the third person 
is eliminated. In this case number 1 is the survivor.

Here is a chart I made showing x and the surviving person's number:

 x   surviving person's number
 1   1
 2   1
 3   3
 4   1
 5   3
 6   5
 7   7
 8   1
 9   3
10   5
11   7
12   9
13  11
14  13
15  15
16   1

The pattern shows that the answer increases by 2 along the odd 
numbers but 'restarts' at one every time x is a power of 2. From this 
I obtained the equation 2(x-the closest power of two less than or 
equal to x)+1 = the winner's number.

I would like to know if there is a way to rewrite this equation 
without using any words.

Date: 04/19/2003 at 23:07:37
From: Doctor Carbon
Subject: Re: Determining an equation from a series

Hi Jeremy,

This problem is also known as the Josephus problem. A quick search on 
www.google.com for "Josephus problem" yields hundreds of links 
describing the original problem along with its history. You will also 
find relevant entries in the Dr. Math archives:

   Knights of the Round Table
   http://mathforum.org/library/drmath/view/55862.html

   A Circular Massacre
   http://mathforum.org/library/drmath/view/55876.html

Your solution description using words is perfect. The real problem, 
as you have said, is in turning it into a single precise equation (or 
expression) for writing the part about "the closest power of two less 
than or equal to x."

Within a longer description like this, I would look for the part that 
I can write most easily. In this case, "a power of 2" is fairly 
straightforward, and would look like

       n
      2     or    2^n

Our goal, therefore, is to make sure that n is a whole number, and 
that the result of this calculation is less than or equal to x.

You pointed out that you needed a mathematical notation, operation or 
function that shows the closest power of an integer less than or 
equal to another number. I have changed the requirement slightly and 
now we are looking for something that gives whole numbers less than 
or equal to a given number.

I don't know if you have heard of it, but there is something called 
the Floor function. It is defined as the largest integer less than or 
equal to the number you use. The way you use it is this: "Floor of 
2.3 is 2," "Floor of 15/2 is 7."

It is written using a special kind of enclosing bracket, and I will 
try to make it using plain text here:

      |       |
      |  2.3  |   = 2
      |_     _|   

This is the same as saying "Floor(2.3) = 2" or "Floor of 2.3 is 2."

In your case, 2^n should equal the power of 2 closest to but less 
than x, so n could be written using the Floor function on its own.

At this point, we can use the general idea that exponents and 
logarithms are opposites of each other. Therefore, to get a power of 
2 close to but less than x, I could use logarithms to base 2 in this 
way:

        |         |
        | Log (x) |
        |_   2   _|   
    2 ^
     
I hope this helps.

The following link to Eric Weisstein's MathWorld entry on the 
Josephus problem has some variations and historical solutions that 
you might find interesting.

   http://mathworld.wolfram.com/JosephusProblem.html 

On a more philosophical note, my belief is that all mathematical 
notations must have evolved from long-winded natural language 
descriptions.

Write back if you'd like to talk about this some more, or if you have 
any other questions.

- Doctor Carbon, The Math Forum
  http://mathforum.org/dr.math/