: 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 for k =2, and hence we denote by .

Example 5.1

Let and . We have 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.

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

Example 5.2

Let and . We have 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.

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

Once two processes have reached the right end of the line, they move in the opposite direction removing numbersD
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 , where the first process starts with 19 and remove 15. By Example 5.1 , and hence the number 11 that is the third number in the list remains.
Therefore we have .

Then we change the direction again, and remove 7. Then we change the direction again, and remove 3. 11 is the last remaining numberDTherefore .

Theorem 5.1   The linear Josepus problem in both directions satisfies the following recurrence relations.
.

.

.

Proof 1 (1)   We suppose that there are 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 -th number, th number, .... When the two processes have removed numbers, numbers remain. See Graph 5.4.

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

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Graph 5.5 we have .
If = , then by Graph 5.5 we have .
By using the floor function we can express by one equation.
.

(2) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number, ...,while the second process begins to remove the -th number, -th number,.... When the two processes have removed numbers, numbers remain. See Graph 5.6.

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Figure 1.3 we have .
Therefore we have .

(3) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number,..., while the second process begins to remove the -th number, -th number, ... . When the two processes have removed numbers, numbers remain. See Graph 5.7.

Since there are numbers remain, depends on
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 .
Therefore if , then by Graph 5.7 we have .
If , then by Graph 5.7 we have .
Therefore we have

(4) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number, ...,while the second process begins to remove the -th number, the -th number, ... When the two processes have removed numbers, numbers remain. See Graph 5.8.

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Graph 5.8 we have .
Therefore we have .

(5) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number, ..., while the second process begins to remove the -th number, the -th number, .... When the two processes have removed numbers, numbers remain. See Graph 5.9.

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Graph 5.9 we have .
If = , then by Graph 5.9 we have .
Therefore we have
.

(6) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number,..., while the second process begins to remove the -th number, the -th number,.... When the two processes have removed numbers, numbers remain. See Graph 5.10.

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Graph 5.10 we have .
Therefore we have .

(7) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number,...,while the second process begins to remove the -th number, the -th number, .... When the two processes have removed numbers, numbers remain. See Graph 5.11.

Since there are numbers remain, depends on
Note that the first process is moving to the left direction, and the second process to the right.
If = , then by Graph 5.11 we have .
If = , then by Graph 5.11 we have .
Therefore we have
.

(8) We suppose that there are numbers. The first process begins to remove the 2nd number, the 4th number, ... while the second process begins to remove the -th number,the th number, .... When the two processes have removed numbers, numbers remain. See 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 .
If = , then by Graph 5.12 we have .
Therefore we have .

For any , we define , and
. We define the distance between two subsets A, B of by
= Max . 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) = and B(K) = . By (a) of Theorem 5.1 we have
, and hence we have
A(K) = = . When K is sufficiently large, and 2 are negligible. Therefore
It is obvious that the graphs of and look very similar when K is large enough.

Definition 5.1   For any subsets A(K), B(K) of we write if there exist a natural number t and a subset C(K) that depends on K such that and

Remark 5.1   In Example 5.3 . If , the graphs of look very similar when is large enough.

Example 5.4   Let A(K) = , B(K) = and C(K) = .
B(K) - C(K) = { (2n,JLI(2n)), }, and 1 is negligible when K is sufficiently large. Therefore
Since we have N(C(K))=1, by Definition 5.1 we have .

Lemma 5.1   For a sufficiently large number K we have the following relations between subsets of .

Proof 2   By (a) of Theorem 5.1 and the fact that and 2 are negligible when K is large, we have

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

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

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 .

Proof 3   By (a) of Theorem 5.1 and the fact that -2 and are negligible when K is large, we have

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

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.

Proof 4

and hence by Lemma 5.1 we can prove this lemma.

Proof 5

and hence by Lemma 5.2 we can prove this lemma.

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 {, n = 1,2,..,1024} and {, n = 1,2,..,1024}. Please compare these two graphsDThey have the same shape, and this fact has been proved in Theorem 5.2.

Proof 7   It is sufficient to prove that

By Lemma 5.3

By Theorem 5.2

By and we have .

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.

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