Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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.

any other questions.

- Doctor Carbon, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Definitions
High School Discrete Mathematics
High School Number Theory
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search