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

Linear Josephus Problem.

The next one is the linear Josephus Problem.

Definition 3.1   Let $ n$ and $ r$ be natural numbers such that $ k \geq 2$. We put $ n$ numbers on a line. We start counting up from the 1st number and move from left to right removing every $ k$th number. We change the direction when we reach the end of the line. Then we begin removing every $ k$ th number again. We denote by $ JL(n,k)$ the position of the last one that remains.

This problem had been studied for $ k = 2,3$ in [5]. The authors have also studied this problem from a different point of view, and they have discovered many interesting graphs that have self-similarity.

Example 3.1   This is a Mathematica program to calculate $ JL(n,k)$. The following Mathematica function $ jL[n,rs]$ returns the value of $ JL(n,k)$.
jL[n_, rs_] := 
  Block[{p, u}, elim = {}; 
   p = Join[Range[n], Sort[Table[m, {m, 2, n - 1}], Greater]];
      Do[Do[u1 = First[p];
     u2 = First[RotateLeft[p, 1]];
If[u1 == u2, 
p = RotateLeft[p, 2], p = RotateLeft[p, 1]], {s,1,rs - 1}];
        u = First[p];
        p = Rest[p]; elim = Append[elim, u]; 
If[MemberQ[p, u], 
p = Drop[p, Position[p, u][[1]]],], {t, 1, n - 1}];
p[[1]]];

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

Example 3.2   Graph 3.1 and Graph 3.2 are the graphs of the lists {$ JL(n,2)$, n = 1,2,..,1024} and {$ JL(n,2)$, n = 1,2,..,256}. Please compare these two graphsDThey have the same shape, and hence these graphs seem to have Fractal behavior (self-similarity). Note that $ 1024:256$ = $ 4:1$.

Graph 3.1   \includegraphics[height=5cm,clip]{linear21024.eps}

Graph 3.2   \includegraphics[height=5cm,clip]{linear2256.eps}

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

Graph 3.3   \includegraphics[height=5cm,clip]{linear31024.eps}

Graph 3.4   \includegraphics[height=5cm,clip]{linear3455.eps}


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