next up previous
: APPENDIX : The Self-Similarity of the Josephus Problem. : The Linear Josephus Problem

Mathematical Theory of the Linear Josephus Problem in both Directions.

From here we are going to study $ JLI(n,k)$ for k =2, and hence we denote $ JLI(n,2)$ by $ JLI(n)$.

Example 5.1  

Let $ n = 5$ and $ k=2$. We have $ 5$ numbers, and we are going to remove every second number. When the first process removes the number 2, and the second process removes the number 4, then two processes are going to intersect each other. See Graph 5.1.

Graph 5.1   % latex2html id marker 2878
\includegraphics[height=1.cm,clip]{linearexample0.eps}

Here we covered eliminated numbers by the first process and the second process with gray color disks and gray color rectangles respectively Then the first process will removes 5, and the second process removes 1. Therefore 3 remains, and we have $ JLI(5,2) = 3.$

Example 5.2  

Let $ n = 21$ and $ k=2$. We have $ 21$ numbers, and we are going to remove every second number. When the first process removes numbers 2,4,6,8,10, and the second process removes numbers 20, 18, 16, 14, 12, then numbers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 remain. See Graph 5.2.

Graph 5.2   % latex2html id marker 2897
\includegraphics[height=1.15cm,clip]{linearexample1.eps}

Then two processes are going to intersect each other.
When 16 numbers are removed, the numbers 3, 7, 11, 15, 19 remain.

Graph 5.3   % latex2html id marker 2903
\includegraphics[height=1.cm,clip]{linearexample2.eps}

Once two processes have reached the right end of the line, they move in the opposite direction removing numbersD
Then the first process will remove 15,3, and the second process will remove 7, 19. Therefore 11 will remain.
We can also calculate the value of JLI(21) by recursive relation.
Since there are only 5 numbers, the value of JLI(21) depends on JLI(5).
Note that the first process will move to the left and remove 15. Therefore we have the linear Josephus Problem in both direction with numbers $ \{19, 15, 11, 7, 3 \}$, where the first process starts with 19 and remove 15. By Example 5.1 $ JLI(5) = 3$, and hence the number 11 that is the third number in the list remains.
Therefore we have $ JLI(21) = 11$.

Then we change the direction again, and remove 7. Then we change the direction again, and remove 3. 11 is the last remaining numberDTherefore $ JL2(12) = 11$.

Theorem 5.1   The linear Josepus problem in both directions satisfies the following recurrence relations.
$ (a)$ $ JLI(8n) = 8n+2-4JLI(2n)+ \lfloor JLI(2n)/(n+1)\rfloor $ .
$ (b)$ $ JLI(8n+1) = 8n+5-4JLI(2n+1).$
$ (c)$ $ JLI(8n+2) = 4JLI(2n+1)-3- \lfloor JLI(2n+1)/(n+2)\rfloor.$
$ (d)$ $ JLI(8n+3) = 8n+7-4JLI(2n+1).$
$ (e)$ $ JLI(8n+4) =8n+8-4JLI(2n+2)+ \lfloor JLI(2n+2)/(n+2)\rfloor $ .
$ (f)$ $ JLI(8n+5) = 8n+7-4JLI(2n+1).$
$ (g)$ $ JLI(8n+6) = 8n+10-4JLI(2n+2)+ \lfloor (JLI(2n+2)/(n+2)\rfloor $ .
$ (h)$ $ JLI(8n+7) = 4JLI(2n+2)-3$

Proof 1 (1)   We suppose that there are $ 8n$ numbers. The first process starts counting up from the first number and remove the 2nd, 4th,... , while the second process starts counting down from the n-th number and remove the $ (8n-1)$-th number, $ (8n-3)$th number, .... When the two processes have removed $ 4n$ numbers, $ 4n$ numbers remain. See Graph 5.4.

Graph 5.4   \includegraphics[height=1.1cm,clip]{linear1.eps}

After this, the two processes are going to intersect each other.
When $ 6n$ numbers are removed, $ 2n$ numbers remain. See Graph 5.5.

Graph 5.5   \includegraphics[height=1.1cm,clip]{linear2.eps}

Since there are $ 2n$ numbers remain, $ JLI(8n)$ depends on $ JLI(2n).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n)$ = $ 1,2,...,n$, then by Graph 5.5 we have $ JLI(8n) = 8n-2, 8n-5, ...,4n+2$.
If $ JLI(2n)$ = $ n+1,n+2,...,2n$, then by Graph 5.5 we have $ JLI(8n) = 4n-1, 4n-5, ...,3$.
By using the floor function we can express $ JLI(8n)$ by one equation.
$ JLI(8n) = 8n+2-4JLI(2n)+ \lfloor JLI(2n)/(n+1)\rfloor $ .

(2) We suppose that there are $ 8n+1$ numbers. The first process begins to remove the 2nd number, the 4th number, ...,while the second process begins to remove the $ 8n$-th number, $ 8n-2$-th number,.... When the two processes have removed $ 6n$ numbers, $ 2n+1$ numbers remain. See Graph 5.6.
\includegraphics[height=1.1cm,clip]{linear3.eps}

Graph 5.6  

Since there are $ 2n+1$ numbers remain, $ JLI(8n+1)$ depends on $ JLI(2n+1).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n+1)$ = $ 1,2,...,2n+1$, then by Figure 1.3 we have $ JLI(8n+1) = 8n+1,8n-3, ...,1$.
Therefore we have $ JLI(8n+1) = 8n+5-4JLI(2n+1)$.

(3) We suppose that there are $ 8n+2$ numbers. The first process begins to remove the 2nd number, the 4th number,..., while the second process begins to remove the $ 8n+1$-th number, $ 8n-1$-th number, ... . When the two processes have removed $ 6n+1$ numbers, $ 2n+1$ numbers remain. See Graph 5.7.
\includegraphics[height=1.1cm,clip]{linearboth8n2.eps}

Graph 5.7  

Since there are $ 2n+1$ numbers remain, $ JLI(8n+2)$ depends on $ JLI(2n+1).$
Note that the original first process is moving to the left direction, and the original second process to the right.
Next the 5th number will be removed by the original second process.
Therefore it is easier for us to calculate if we think that the new first process is moving to right direction and remove the 5th number and the new second process is going to remove $ 8n-4$.
Therefore if $ JLI(2n+1) = 1, 2, ...,n+1$, then by Graph 5.7 we have $ JLI(8n+2) = 1, 5, ..., 4n-1$.
If $ JLI(2n+1) = n+2,n+3,....,2n+1$, then by Graph 5.7 we have $ JLI(8n) = 4n+4, 4n+8, ..., 8n$.
Therefore we have
$ JLI(8n+2) = 4JLI(2n+1)-3- \lfloor JLI(2n+1)/(n+2)\rfloor.$

(4) We suppose that there are $ 8n+3$ numbers. The first process begins to remove the 2nd number, the 4th number, ...,while the second process begins to remove the $ 8n+2$-th number, the $ 8n$-th number, ... When the two processes have removed $ 6n+2$ numbers, $ 2n+1$ numbers remain. See Graph 5.8.
\includegraphics[height=1.1cm,clip]{linearboth8n3.eps}

Graph 5.8  

Since there are $ 2n+1$ numbers remain, $ JLI(8n+3)$ depends on $ JLI(2n+1).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n+1)$ = $ 1,2,...,2n+1$, then by Graph 5.8 we have $ JLI(8n+1) = 8n+3,8n-1, ...,3$.
Therefore we have $ JLI(8n+3) = 8n+7-4JLI(2n+1).$.

(5) We suppose that there are $ 8n+4$ numbers. The first process begins to remove the 2nd number, the 4th number, ..., while the second process begins to remove the $ 8n+3$-th number, the $ 8n+1$-th number, .... When the two processes have removed $ 6n+2$ numbers, $ 2n+2$ numbers remain. See Graph 5.9.
\includegraphics[height=1.1cm,clip]{linearboth8n4.eps}

Graph 5.9  

Since there are $ 2n+2$ numbers remain, $ JLI(8n+4)$ depends on $ JLI(2n+2).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n+2)$ = $ 1,2,...,n+1$, then by Graph 5.9 we have $ JLI(8n+4) = 8n+4,8n, ...,4n+4$.
If $ JLI(2n+2)$ = $ n+2,n+3,...,2n+2$, then by Graph 5.9 we have $ JLI(8n+4) = 4n+1, 4n-3,...,1$.
Therefore we have
$ JLI(8n+4) =8n+8-4JLI(2n+2)+ \lfloor JLI(2n+2)/(n+2)\rfloor $ .

(6) We suppose that there are $ 8n+5$ numbers. The first process begins to remove the 2nd number, the 4th number,..., while the second process begins to remove the $ 8n+4$-th number, the $ 8n+1$-th number,.... When the two processes have removed $ 6n+4$ numbers, $ 2n+1$ numbers remain. See Graph 5.10.
\includegraphics[height=1.1cm,clip]{linearboth8n5.eps}

Graph 5.10  

Since there are $ 2n+1$ numbers remain, $ JLI(8n+5)$ depends on $ JLI(2n+1).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n+1)$ = $ 1,2,...,2n+1$, then by Graph 5.10 we have $ JLI(8n+5) = 8n+3,8n-1, ...,3$.
Therefore we have $ JLI(8n+5) = 8n+7-4JLI(2n+1)$.

(7) We suppose that there are $ 8n+6$ numbers. The first process begins to remove the 2nd number, the 4th number,...,while the second process begins to remove the $ 8n+5$-th number, the $ 8n+3$-th number, .... When the two processes have removed $ 6n+4$ numbers, $ 2n+2$ numbers remain. See Graph 5.11.
\includegraphics[height=1.1cm,clip]{linearboth8n6.eps}

Graph 5.11  

Since there are $ 2n+2$ numbers remain, $ JLI(8n+6)$ depends on $ JLI(2n+2).$
Note that the first process is moving to the left direction, and the second process to the right.
If $ JLI(2n+2)$ = $ 1,2,...,n+1$, then by Graph 5.11 we have $ JLI(8n+6) = 8n+6,8n+2, ...,4n+6$.
If $ JLI(2n+2)$ = $ n+2,n+3,...,2n+2$, then by Graph 5.11 we have $ JLI(8n+6) = 4n+3, 4n-1,...,3$.
Therefore we have
$ JLI(8n+6) = 8n+10-4JLI(2n+2)+ \lfloor (JLI(2n+2)/(n+2)\rfloor $ .

(8) We suppose that there are $ 8n+7$ numbers. The first process begins to remove the 2nd number, the 4th number, ... while the second process begins to remove the $ 8n+6$-th number,the $ 8n+4$th number, .... When the two processes have removed $ 6n+5$ numbers, $ 2n+2$ numbers remain. See Graph 5.12.
\includegraphics[height=1.1cm,clip]{linearboth8n7.eps}

Graph 5.12  

Note that the original first process is moving to the left direction, and the original second process to the right.
Next the 5th number will be removed by the original second process.
Therefore it is easier for us to calculate if we think that the new first process is moving to right direction and remove the 5th number and the new second process is going to remove $ 8n+1$.
If $ JLI(2n+2)$ = $ 1,2,...,2n+2$, then by Graph 5.12 we have $ JLI(8n+7) = 1,5,...,8n+5$.
Therefore we have $ JLI(8n+7) = 4JLI(2n+2)-3$.

For any $ x = (x_{1},x_{2})$, $ y = (y_{1},y_{2})$ $ \in R^2$ we define $ d(x, y) = \sqrt{(x_1-y_1)^2+(x_2-y_2)^2} $, and
$ d(x,A) = \inf_{y\in A }d(x,y)$. We define the distance between two subsets A, B of $ R^2$ by
$ \delta (A,B)$ = Max $ ( \sup_{x\in A }d(x,B), \sup_{y\in B }d(y,A) )$. For any set A we denote by N(A) the number of elements in A.

Example 5.3   Let K be a natural number, and let A(K) = $ \{(8n, 8n-JLI(8n)), n \leq K \} $ and B(K) = $ \{(8n, 4JLI(2n)), n \leq K \} $. By (a) of Theorem 5.1 we have
$ JLI(8n) = 8n+2-4JLI(2n)+ \lfloor JLI(2n)/(n+1)\rfloor $, and hence we have
A(K) = $ \{(8n, 8n-JLI(8n)), n \leq K \} $ = $ \{(8n, 4JLI(2n)-2-\lfloor JLI(2n)/(n+1)\rfloor), n \leq K \} $. When K is sufficiently large, $ \lfloor JLI(2n)/(n+1)\rfloor), n \leq K \}$ and 2 are negligible. Therefore $ \lim_{K \to \infty} \frac{ \delta(A(K),B(K))}{K} = 0.$
It is obvious that the graphs of $ A(K)$ and $ B(K)$ look very similar when K is large enough.

Definition 5.1   For any subsets A(K), B(K) of $ R^2$ we write $ A(K) \sim B(K)$ if there exist a natural number t and a subset C(K) that depends on K such that $ N(C(K)) \leq t$ and $ \lim_{K \to \infty} \frac{ \delta(A(K)-C(K),B(K)-C(K))}{K} = 0.$

Remark 5.1   In Example 5.3 $ A(K) \sim B(K)$. If $ A(K) \sim B(K)$, the graphs of $ A(K), B(K)$ look very similar when $ K$ is large enough.

Example 5.4   Let A(K) = $ \{(2n+1, JLI(2n)), n \leq K \} $, B(K) = $ \{(2n+2, JLI(2n+2)), n \leq K \} $ and C(K) = $ \{(2K+2, JLI(2K+2)) \} $.
B(K) - C(K) = { (2n,JLI(2n)), $ n \leq K$ }, and 1 is negligible when K is sufficiently large. Therefore $ \lim_{K \to \infty} \frac{ \delta(A(K),B(K)-C(K))}{K} = 0.$
Since we have N(C(K))=1, by Definition 5.1 we have $ A(K) \sim B(K)$.

Lemma 5.1   For a sufficiently large number K we have the following relations between subsets of $ R^2$.
$ (a)$

$\displaystyle \{(8 n, JLI (8 n) ), n \leq K \}$    
$\displaystyle \sim \{(8n+4, JLI(8n+4)), n \leq K \}$    
$\displaystyle \sim \{(8n+6, JLI(8n+6)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, 2n-JLI(2n)), n \leq K \} .$    

$ (b)$

$\displaystyle \{(8n+1, JLI(8n+1)), n \leq K\}$    
$\displaystyle \sim \{(8n+3, JLI(8n+3)), n \leq K\}$    
$\displaystyle \sim \{(8n+5, JLI(8n+5)), n \leq K\}$    
$\displaystyle \sim 4\{(2n+1, 2n+1-JLI(2n+1)), n \leq K \} .$    

$ (c)$

$\displaystyle \{(8n+2, JLI(8n+2)),n \leq K\}$    
$\displaystyle \sim 4\{(2n+1, JLI(2n+1)), n \leq K \} .$    

$ (d)$

$\displaystyle \{(8n+7, JLI(8n+7)), n \leq K \}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

Proof 2   $ (1)$ By (a) of Theorem 5.1 and the fact that $ \lfloor JLI (2 n)/(n + 1)\rfloor$ and 2 are negligible when K is large, we have

$\displaystyle \{(8 n, JLI (8 n) ), n \leq K \}$    
$\displaystyle = \{(8 n, 8 n + 2 - 4 JLI (2 n) +\lfloor JLI (2 n)/(n + 1)\rfloor ), n \leq K \}$    
$\displaystyle \sim \{ (8 n, 8 n - 4 JLI (2 n) ), n \leq K \}$    
$\displaystyle = 4\{ (2n, 2n - JLI (2 n) ), n \leq K \}.$    

$ (2)$ By (b) of Theorem 5.1 and the fact that 1,4, and 5 are negligible when K is large, we have

$\displaystyle \{(8n+1, JLI(8n+1)), n \leq K\}$    
$\displaystyle = \{ (8 n+1, 8n+5-4JLI(2n+1) ) , n\leq K \}$    
$\displaystyle \sim \{ (8 n+4, 8n+4 - 4JLI(2n+1) ) , n \leq K \}$    
$\displaystyle = 4 \{ (2 n+1, 2n+1-JLI(2n+1)) , n \leq K \}.$    

Similarly we can prove the following (3), (4),...,(8).
$ (3)$

$\displaystyle \{(8n+2, JLI(8n+2)),n \leq K\}$    
$\displaystyle = \{ (8 n + 2, 4 JLI (2 n + 1) - 3 -\lfloor JLI (2 n + 1)/(n + 2)\rfloor ), n \leq K \}$    
$\displaystyle \sim \{ (8 n + 4, 4 JLI (2 n + 1) ), n \leq K \}$    
$\displaystyle = 4 \{ (2 n + 1, JLI (2 n + 1) ), n \leq K \}.$    

$ (4)$

$\displaystyle \{ (8 n + 3, JLI (8 n +3)), n \leq K\}$    
$\displaystyle = \{(8n + 3, 8n+7-4JLI(2n+1)), n \leq K\}$    
$\displaystyle \sim \{ (8 n+4, 8n+4 - 4JLI(2n+1) ) , n \leq K \}$    
$\displaystyle \sim 4\{(2n+1, 2n+1-JLI(2n+1)), n \leq K \} .$    

$ (5)$

$\displaystyle \{ (8 n + 4, JLI (8 n + 4), n \leq K\}$    
$\displaystyle = \{ (8 n + 4, 8n+8-4JLI(2n+2)+ \lfloor JLI(2n+2)/(n+2) \rfloor ), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 8, 8n+8-4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, 2n+2-JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, 2n-JLI(2n)), n \leq K \} .$    

$ (6)$

$\displaystyle \{ (8 n + 5, JLI (8 n + 5), n \leq K\}$    
$\displaystyle = \{ (8 n + 5, 8n+7-4JLI(2n+1)), n \leq K\}$    
$\displaystyle \sim \{ (8 n+4, 8n+4 - 4JLI(2n+1) ) , n \leq K \}$    
$\displaystyle = 4 \{ (2 n+1, 2n+1-JLI(2n+1)) , n \leq K \}.$    

$ (7)$

$\displaystyle \{ (8 n + 6, JLI (8 n+ 6)), n \leq K\}$    
$\displaystyle =\{ (8 n + 6, 8n+10-4JLI(2n+2)+\lfloor (JLI(2n+2)/(n+2)\rfloor ), n \leq K\}$    
$\displaystyle = \{ (8 n + 8, 8n+8-4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, 2n+2-JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, 2n-JLI(2n)), n \leq K \} .$    

$ (8)$

$\displaystyle \{ (8 n + 7, JLI (8 n + 7), n \leq K\}$    
$\displaystyle = \{ (8 n + 7, 4JLI(2n+2)-3), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 8, 4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

By (1), (5) and (7) we can prove (a) of this lemma.
By (2), (4) and (6) we can prove (b) of this lemma.
By (3) we can prove (c) of this lemma.
By (8) we can prove (d) of this lemma.

Lemma 5.2   For a sufficiently large number K we have the following relations between subsets of $ R^2$.
$ (a)$

$\displaystyle \{ (8 n, 8 n - JLI (8 n) ), n \leq K\}$    
$\displaystyle \sim \{(8 n + 4, 8 n + 4 - JLI (8 n + 4), n \leq K\}$    
$\displaystyle \sim \{(8 n + 6, 8 n + 6 - JLI (8 n + 6), n \leq K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

$ (b)$

$\displaystyle \{ (8 n+1, 8 n+1 - JLI (8 n+1) ), n \leq K\}$    
$\displaystyle \sim \{(8 n + 3, 8 n + 3 - JLI (8 n + 3), n \leq K\}$    
$\displaystyle \sim \{(8 n + 5, 8 n + 5 - JLI (8 n + 5), n \leq K\}$    
$\displaystyle \sim 4\{(2n+1, JLI(2n+1)), n \leq K \} .$    

$ (c)$

$\displaystyle \{ (8 n+2, 8 n+2 - JLI (8 n+2) ), n \leq K\}$    
$\displaystyle \sim 4\{(2n+1, 2n+1-JLI(2n+1)), n \leq K \} .$    

$ (d)$

$\displaystyle \{ (8 n+7, 8 n+7 - JLI (8 n+7) ), n \leq K\}$    
$\displaystyle \sim 4\{ (2n+2 , 2n+2-JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, 2n-JLI(2n)), n \leq K \} .$    

Proof 3   $ (1)$ By (a) of Theorem 5.1 and the fact that -2 and $ \lfloor JLI (2 n)/(n + 1)\rfloor$ are negligible when K is large, we have

$\displaystyle \{ (8 n, 8 n - JLI (8 n) ), n \leq K\}$    
$\displaystyle = \{ (8 n, 8 n - ( 8 n + 2 - 4 JLI (2 n)$    
$\displaystyle +\lfloor JLI (2 n)/(n + 1)\rfloor ) ), n \leq K\}$    
$\displaystyle = \{ (8 n, -2 + 4 JLI (2 n) -\lfloor JLI (2 n)/(n + 1)\rfloor )$    
$\displaystyle \sim \{ (8 n, 4 JLI (2 n)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

Similarly we can prove the following (2), (3), ...,(8).
$ (2)$

$\displaystyle \{ (8 n+1, 8 n+1 - JLI (8 n+1) ), n \leq K\}$    
$\displaystyle = \{(8 n+1, 8 n+1 - ( 8n+5-4JLI(2n+1) ) , n \leq K\}$    
$\displaystyle \sim \{ (8 n + 4, 4 JLI (2 n + 1) ), n \leq K \}$    
$\displaystyle = 4 \{ (2 n + 1, JLI (2 n + 1) ), n \leq K \}.$    

$ (3)$

$\displaystyle \{ (8 n+2, 8 n+2 - JLI (8 n+2) ), n \leq K\}$    
$\displaystyle = \{(8 n + 2, 8 n + 2 - ( 4JLI(2n+1)-3- \lfloor JLI(2n+1)/(n+2)\rfloor )), n \leq K\}$    
$\displaystyle \sim \{ (8 n+4, 8n+4 - 4JLI(2n+1) ) , n \leq K \}$    
$\displaystyle = 4 \{ (2 n+1, 2n+1-JLI(2n+1)) , n \leq K \}.$    

$ (4)$

$\displaystyle \{(8 n + 3, 8 n + 3 - JLI (8 n +3)), n \leq K\}$    
$\displaystyle = \{(8 n + 3, 8 n + 3 - (8n+7-4JLI(2n+1))), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 4, 4 JLI (2 n + 1) ), n \leq K \}$    
$\displaystyle = 4 \{ (2 n + 1, JLI (2 n + 1) ), n \leq K \}.$    

$ (5)$

$\displaystyle \{(8 n + 4, 8 n + 4 - JLI (8 n + 4), n \leq K\}$    
$\displaystyle = \{(8 n + 4, 8 n + 4 - (8n+8-4JLI(2n+2)+$    
$\displaystyle \lfloor JLI(2n+2)/(n+2) \rfloor])), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 8, 4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

$ (6)$

$\displaystyle \{(8 n + 5, 8 n + 5 - JLI (8 n + 5), n \leq K\}$    
$\displaystyle = \{(8 n + 5, 8 n + 5 - (8n+7-4JLI(2n+1)), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 4, 4 JLI (2 n + 1) ), n \leq K \}$    
$\displaystyle = 4 \{ (2 n + 1, JLI (2 n + 1) ), n \leq K \}.$    

$ (7)$

$\displaystyle \{(8 n + 6, 8 n + 6 - JLI (8 n + 6), n \leq K\}$    
$\displaystyle =\{(8 n + 6, 8 n + 6 - (8n+10-4JLI(2n+2)+$    
$\displaystyle \lfloor (JLI(2n+2)/(n+2)\rfloor)), n \leq K\}$    
$\displaystyle \sim \{ (8 n + 8, 4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} .$    

$ (8)$

$\displaystyle \{(8 n + 7, 8 n + 7 - JLI (8 n + 7), n \leq K\}$    
$\displaystyle = \{(8 n + 7, 8 n + 7 - (4JLI(2n+2)-3), n \leq K \}$    
$\displaystyle = \{ (8 n + 8, 8n+8-4JLI(2n+2)), n \leq K\}$    
$\displaystyle = 4\{ (2n + 2, 2n+2-JLI(2n+2)), n \leq K\}$    
$\displaystyle \sim 4\{(2n, 2n-JLI(2n)), n \leq K \} .$    

By (1), (5) and (7) we can prove (a) of this lemma.
By (2), (4) and (6) we can prove (b) of this lemma.
By (3) we can prove (c) of this lemma.
By (8) we can prove (d) of this lemma.

Lemma 5.3  

$\displaystyle \{(n, JLI (n)), n \leq 8K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} \cup 4\{(2n+1, JLI(2n+1)), n \leq K\}$    
$\displaystyle \cup 4\{(2n, 2n-JLI(2n)), n \leq K\}$    
$\displaystyle \cup 4\{(2n+1, 2n+1-JLI(2n+1)), n \leq K\}.$    

Proof 4  

\begin{gather*}\begin{array}{l} \{(n, JLI (n)), n \leq 8K\} \\ = \{(8n, JLI(8n))...
...JLI(8n+6)), n < K\} \cup \{(8n+7, JLI(8n+7)), n < K \}, \end{array}\end{gather*}    

and hence by Lemma 5.1 we can prove this lemma.

Lemma 5.4  

$\displaystyle \{(n, n-JLI (n)), n \leq 8K\}$    
$\displaystyle \sim 4\{(2n, JLI(2n)), n \leq K \} \cup 4\{(2n+1, JLI(2n+1)), n \leq K\}$    
$\displaystyle \cup 4\{(2n, 2n-JLI(2n)), n \leq K\}$    
$\displaystyle \cup 4\{(2n+1, 2n+1-JLI(2n+1)), n \leq K\}.$    

Proof 5  

\begin{gather*}\begin{array}{l} \{(n, n-JLI (n)), n \leq 8K\} =\\ \{(8n, 8n-JLI(...
...6)), n < K\}\\ \cup \{(8n+7, 8n+7-JLI(8n+7)), n < K \}, \end{array}\end{gather*}    

and hence by Lemma 5.2 we can prove this lemma.

Theorem 5.2  

$\displaystyle \{(n, JLI (n)), n \leq K\}$    
$\displaystyle \sim \{(n, n-JLI(n)), n \leq K \}.$    

Proof 6   This is direct from Lemma 5.3 and Lemma 5.4.

Example 5.5   Graph 5.13 and Graph 5.14 are the graphs of the lists {$ JLI(n)$, n = 1,2,..,1024} and {$ n-JLI(n)$, n = 1,2,..,1024}. Please compare these two graphsDThey have the same shape, and this fact has been proved in Theorem 5.2.

Graph 5.13   \includegraphics[height=5cm,clip]{linearboth21024.eps}

Graph 5.14   \includegraphics[height=5cm,clip]{linearbreverse.eps}

Theorem 5.3  

$\displaystyle \{(n, JLI (n)), n \leq 4K\} = 4\{(m, JLI(m)), n \leq K \}.$    

Proof 7   It is sufficient to prove that
$ \{(n, JLI (n)), n \leq 8K\} $

$\displaystyle \sim 4\{(m, JLI(m)), n \leq 2K \}.$ (5.1)

By Lemma 5.3
$ \{(n, JLI (n)), n \leq 8K\} $

$\displaystyle \sim 4\{(m, JLI(m)), n \leq 2K \} \cup 4\{(m, m-JLI(m)), n \leq 2K \}.$ (5.2)

By Theorem 5.2

$\displaystyle \{(m, JLI(m)), n \leq 2K \} \sim \{(m, m-JLI(m)), n \leq 2K \}.$ (5.3)

By % latex2html id marker 3566
$ (\ref{selfsim1})$ and % latex2html id marker 3568
$ (\ref{selfsim2})$ we have % latex2html id marker 3570
$ (\ref{th})$.

By Theorem 5.3 we have proved the self-similarity in Example 4.2. We have not proved the self-similarity of the graphs in other examples.


next up previous
: APPENDIX : The Self-Similarity of the Josephus Problem. : The Linear Josephus Problem