The Linear Josephus Problem in Both Directions.

This is the linear Josephus problem in both directions. This variant has been introduced by the authors, but they have not published it in any mathematical journal.

The Self-Similarity of the Josephus Problems

Definition 4.1   Let $n$ and $k$ be natural numbers such that $k \geq 2$. We put $n$ numbers on a line. two numbers are to be removed at the same time, but two processes of elimination go for different directions. 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 the $(n-k+1)$-th, $(n-2k+1)$-th, $(n-3k+1)$-th number, ... are to be removed. We suppose that the first process comes first and the second process second at every stage. We change the direction when we reach the end of the line. Then we begin removing every $k$ th number again.
We call this the linear Josephus Problem in both directions. We denote the position of the survivor by $JLI(n,k)$.

Example 4.1   This is a Mathematica program to calculate $JLI(n,k)$. The following Mathematica function $linearinter[n, k]$ returns the value of $JLI(n,k)$.

linearinter[n_, h_] := 
  Block[{p, q, u, rs}, rs = h - 1; elim = {}; elim2 = {}; 
p = Join[Range[n], Sort[Table[m, {m, 2, n - 1}], Greater]];
q = Reverse[Join[Reverse[Range[n]], Table[k, {k, 2, n - 1}]]];
      Do[Do[u1 = First[p];
     u2 = First[RotateLeft[p, 1]];
     If[u1 == u2, p = RotateLeft[p, 2], p = RotateLeft[p, 1]],
 {s, 1, rs}];
u = First[p];
p = Rest[p]; elim = Append[elim, u]; 
If[MemberQ[p, u], p = Delete[p, Position[p, u]],];
If[MemberQ[q, u], q = Delete[q, Position[q, u]],];
If[Length[Union[p]] == 1, Break[],];
Do[u1 = Last[q];
    u2 = Last[RotateRight[q, 1]];
If[u1 == u2, q = RotateRight[q, 2], q = RotateRight[q, 1]], 
{s,1, rs}];
        u = Last[q];
        q = Drop[q, -1]; elim2 = Append[elim2, u];
If[MemberQ[q, u], q = Delete[q, Position[q, u]],]; 
If[MemberQ[p, u], p = Delete[p, Position[p, u]],]; 
If[Length[Union[q]] == 1, Break[],], {t, 1, Ceiling[n/2]}];
   p[[1]]];

By using the Mathematica function in Example 4.1 we can make the graph of the list {JLI(n,k), n = 1,2,3,... }.

Example 4.2   Graph 4.1 and Graph 4.2 are the graphs of the lists {$JLI(n,2)$, n = 1,2,..,1024} and {$JLI(n,2)$, n = 1,2,..,256}. 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$ is approximately equal to $4:1$.

Graph 4.1  

Graph 4.2  

We are going to prove that the graph of $JLI(n,2)$ in Example 4.2 has the self-similarity with the ratio of $4:1$ in the next section.

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 4.3   Graph 4.3 and Graph 4.4 are the graphs of the lists {$JLI(n,3)$, n = 1,2,..,1024} and {$JLI(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 4.3  

Graph 4.4  

Example 4.4   Graph 4.5 and Graph 4.6 are the graphs of the lists {$JLI(n,4)$, n = 1,2,..,1024} and {$JLI(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 4.5  

Graph 4.6  

Example 4.5   Graph 4.7 and Graph 4.8 are the graphs of the lists {$JLI(n,5)$, n = 1,2,..,1024} and {$JLI(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 4.7  

Graph 4.8  

Example 4.6   Graph 4.9 and Graph 4.10 are the graphs of the lists {$JLI(n,6)$, n = 1,2,..,1024} and {$JLI(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 4.9  

Graph 4.10  

Example 4.7   Graph 4.11 and Graph 4.12 are the graphs of the lists {$JLI(n,7)$, n = 1,2,..,1024} and {$JLI(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 4.11  

Graph 4.12  

Example 4.8   Graph 4.13 and Graph 4.14 are the graphs of the lists {$JLI(n,8)$, n = 1,2,..,1024} and {$JLI(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 4.13  

Graph 4.14  

Example 4.9   Graph 4.15 and Graph 4.16 are the graphs of the lists {$JLI(n,9)$, n = 1,2,..,1024} and {$JLI(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 4.15  

Graph 4.16  

Example 4.10   Graph 4.17 and Graph 4.18 are the graphs of the lists {$JLI(n,10)$, n = 1,2,..,1024} and {$JLI(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 4.17  

Graph 4.18  

Example 4.11   Graph 4.19 and Graph 4.20 are the graphs of the lists {$JLI(n,11)$, n = 1,2,..,1024} and {$JLI(n,11)$, n = 1,2,..,846}. Please compare these two graphs．They have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $1024:846$ is approximately equal to $121:100$.

Graph 4.19  

Graph 4.20