next up previous
: The Josephus Problem in both directions. : The Self-Similarity of the Josephus Problem.

Introduction and the traditional Josephus Problem.

In this article we are going to study variants of the Josephus Problem and interesting properties of the graphs produced by these variants.
These variants have interesting recursive relations and beautiful self-similarities of the graphs.
The authors have studied variants of the Josephus Problem, and have published our result in [4], and our article is going to be published in [6].
In this article the authors are going to present new results of our research on the variants of the Josephus Problem.

With a proper computer program it becomes very easy to study this variant of the Josephus Problem. Please read the appendix of this article for the programs of the Josephus Problem.

First we are going to study the traditional Josephus Problem.

Definition 1.1   Let $ n$ and $ r$ be natural numbers such that $ r \geq 2$. We put $ n$ numbers in a circle, and we are going to remove numbers. We start counting up form the 1 st number, and the $ r$-th, $ 2r$-th, $ 3r$-th number, ... are to be removed. We denote by $ Jr(n)$ the position of the last number.

When $ r = 2$, then the function $ Jr(m)$ has very simple recursive relations.

Theorem 1.1   $ J2(2m) = 2J2(m) - 1$ and $ J2(2m + 1) = 2J2(m) + 1.$

This is a well known formula. See [2].
Since $ J2(1) = 1$, by Theorem1.1 we can calculate $ J2(n)$ for any natural number $ n$.

Example 1.1   The graph of the list {J2(n) , $ n = 1$, 2, 3, ..., 100}.

Graph 1.1   \includegraphics[height=3.5cm,clip]{rims1.eps}

The horizontal coordinate is for the number of numbers involved in the game, and the vertical coordinate is for the last number. For example, by $ J2(75) = 23$ we have the point $ (75,23)$ in the graph.
As you can see, the graph of the function $ J2(n)$ is very simple. It is interesting to compare this to the graphs in the following sections.

next up previous
: The Josephus Problem in Both Directions : The Self-Similarity of the Josephus Problem.