The Josephus Problem in both Directions.

Here we are going to introduce the Josephus Problem in both directions. This variant of the Josephus Problem has been introduced by the authors in [1].

Definition 2.1   In this variant of the Josephus Problem two numbers are to be removed at the same time, but two processes of elimination go for different directions. Let $n$ and $k$ be natural numbers such that $k \geq 2$. Suppose that there are $n$-numbers. Then the first process of elimination starts counting up from the first number and remove the $k$-th, $2k$-th, $3k$-th number, ... . The second process counts down from the $n$-th number and remove the $(n-k+1)$-th, $(n-2k+1)$-th, $(n-3k+1)$-th number, ... . We suppose that the first process comes first and the second process second at every stage. We denote the position of the survivor by $JI(n,k)$.

The authors studied this varinat of Josephus problem for $k=2$, and discovered some very interesting self-similarity in the problem. See [6]

Example 2.1   This is a Mathematica program to calculate $JI(n,k)$. The following Mathematica function $joseboth[n,rs]$ returns the value of $JI(n,k)$.

joseboth[m_, mm_] := Block[{t, p, q, u, v, w}, w = mm - 1;
 t = Range[m];
 p = t;
 q = t;
 Do[p = RotateLeft[p, w];
  u = First[p];
  p = Rest[p];
  q = Drop[q, Position[q, u][[1]]];
  If[Length[p] == 1, Break[],];
  q = RotateRight[q, w];
  v = Last[q];
  q = Drop[q, -1];
  p = Drop[p, Position[p, v][[1]]];
  If[Length[q] == 1, Break[],], {n, 1, Ceiling[m/2]}]; p[[1]]];

By using the Mathematica function in Example 2.1 we can make the list { JI(n,k), n = 1,2,... }.

Example 2.2   Graph 2.1 and Graph 2.2 are the graphs of the lists {$JI(n,2)$, n = 1,2,..,1024} and {$JI(n,2)$, n = 1,2,..,256}.
The horizontal coordinate is for the number of numbers in the game, and the vertical coordinate is for the number that remains.
Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:256$ = $4:1$. This can be seen as the ratio of the self-similarity of the graph.

Graph 2.1  

Graph 2.2  

The authors could prove that the graph of $JI(n,2)$ in Example 2.2 has the self-similarity with the ratio of $4:1$ in [6]. The authors have not proved the existence of the self-similarity for $k = 3,4,5,...$. As to these problems the authors are going to present only graphs, and the graphs seem to have the self-similarity.

Example 2.3   Graph 2.3 and Graph 2.4 are the graphs of the lists {$JI(n,3)$, n = 1,2,..,1024} and {$JI(n,3)$, n = 1,2,..,455}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:455$ is approximately equal to $9:4$.

Graph 2.3  

Graph 2.4  

Example 2.4   Graph 2.5 and Graph 2.6 are the graphs of the lists {$JI(n,4)$, n = 1,2,..,1024} and {$JI(n,4)$, n = 1,2,..,580}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:580$ is approximately equal to $16:9$.

Graph 2.5  

Graph 2.6  

Example 2.5   Graph 2.7 and Graph 2.8 are the graphs of the lists {$JI(n,5)$, n = 1,2,..,1024} and {$JI(n,5)$, n = 1,2,..,654}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:654$ is approximately equal to $25:16$.

Graph 2.7  

Graph 2.8  

Example 2.6   Graph 2.9 and Graph 2.10 are the graphs of the lists {$JI(n,6)$, n = 1,2,..,1024} and {$JI(n,6)$, n = 1,2,..,710}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:710$ is approximately equal to $36:25$.

Graph 2.9  

Graph 2.10  

Example 2.7   Graph 2.11 and Graph 2.12 are the graphs of the lists {$JI(n,7)$, n = 1,2,..,1024} and {$JI(n,7)$, n = 1,2,..,751}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:751$ is approximately equal to $49:36$.

Graph 2.11  

Graph 2.12  

Example 2.8   Graph 2.13 and Graph 2.14 are the graphs of the lists {$JI(n,8)$, n = 1,2,..,1024} and {$JI(n,8)$, n = 1,2,..,783}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:783$ is approximately equal to $64:49$.

Graph 2.13  

Graph 2.14  

Example 2.9   Graph 2.15 and Graph 2.16 are the graphs of the lists {$JI(n,9)$, n = 1,2,..,1024} and {$JI(n,9)$, n = 1,2,..,808}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:808$ is approximately equal to $81:64$.

Graph 2.15  

Graph 2.16  

Example 2.10   Graph 2.17 and Graph 2.18 are the graphs of the lists {$JI(n,10)$, n = 1,2,..,1024} and {$JI(n,10)$, n = 1,2,..,828}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:828$ is approximately equal to $100:81$.

Graph 2.17  

Graph 2.18  

From Example 2.2, ..., Example 2.10 the authors can get the following prediction.

Prediction 2.1   The graph of the list {$JI(n,k)$, n = 1,2,..,} has the self-similarity with the ratio of $k^2 : (k-1)^2$.