# An interesting fact about the Josephus Problem in Both Directions.

There is a very interesting fact about the function .

Example 3.1   The list of the sequence is

We denote this sequence modulo 2 by . Then is

We can find a very beautiful pattern if we arrange them as the following.

 (3.1)

 (3.2)

We are going to present a formula for this pattern in Theorem 3.2.

Lemma 3.1 (a)   is odd number for any non-negative integer .
(b) is even if and only if for any natural number .

Proof (a)   By (2),(4),(6) and (8) of Theorem 2.1 we know that is odd number for any odd number .
(b-1) Suppose that for some natural number n. If is even, then By (1) of Theorem 2.1 =1,
which implies that . Then by (1) of Theorem 2.1 Conversely if , then by (1) of Theorem 2.1 we have . Then =1 and by (1) of Theorem 2.1 we know that is even. We have proved (b) for .
(b-2) Suppose that for some natural number n. By the same method that we used in (b-1) we can prove that is even if and only if . Similarly we have if and only if .
(b-3) Suppose that for some natural number n. By the same method that we used in (b-1) we can prove that is even if and only if . Similarly we can prove that
if and only if .
(b-4) Suppose that for some natural number n. By the same method that we used in (b-1) we can prove that is even if and only if . Similarly we can prove that
if and only if

Our aim in this section is to prove the existence of the pattern in . By Lemma 3.1 is even if and only if , and hence it is important to know or not for any natural number .

Lemma 3.2   Suppose that or , then
(a) or ,
(b) or ,
(c) or and
(d) or respectively.
Suppose that or , then
(e) or ,
(f) or ,
(g) or and
(h) or respectively.

Proof   (a) First we suppose that

 (3.3)

By (1) of Theorem 2.1 , and hence by

 (3.4)

By and we have .
Next we suppose that

 (3.5)

By Theorem 2.1 and

 (3.6)

By and we have .
Therefore we have proved (a) of this theorem.
By the similar method we are going to prove (b), (c) and (d).
Suppose that or . Then by Lemma 2.1 , and hence we have or .
(b) By (2) of Theorem 2.1 we have or respectively. Therefore we have proved (b).
(c) By (3) of Theorem 2.1 we have or respectively.
We have proved (c).
(d) By (4) of Theorem 2.1 we have
or respectively. We have proved (d).
Next we are going to prove (e),(f),(g) and (h). Suppose that or .
(e) By (5) of Theorem 2.1 we have or respectively.
We have proved (e).
(f) By (6) of Theorem 2.1 we have or respectively.
We have proved (f).
(g) By (7) of Theorem 2.1 we have or respectively.
We have proved (g).
(h) By (8) of Theorem 2.1 we have or respectively.
We have proved (h).

Definition 3.1   To use Lemma 3.2 we need a function. We define by

for any natural number and

for any non-negative integer .

In short = 0 or 1 if is in the first or the second half of the list . is a useful function when we study the pattern in .

Lemma 3.3   Let be a natural number. (1) . (2) if and only if

Proof   This is direct from Definition 3.1 and Lemma 3.1.

This function has simple recursive relations.

Lemma 3.4   Suppose that or , then
(1) or ,
(2) or 0,
(3) or and
(4) or respectively.
Suppose that or , then
(5) or 0,
(6) or ,
(7) or 0 and
(8) or respectively.

Proof   This is direct from Theorem 3.2 and Definition 3.1.

Example 3.2   The sequence {H(n), n = 1,2,... } has a very beautiful pattern. First we make a triangle with H(n) for n = 1,2,3,..,31.

 (3.7)

We are going to calculate each H(n) using Definition 3.1 and Lemma 3.4.
Since JI(1)=1, JI(2)=1, JI(3) = 3, by Definition 3.1 we have H(1) = 0, H(2) = 0, H(3) = 1.
Since H(1) = 0, let n = 0 and by using (5), (6), (7) and (8) of Lemma 3.4 we have {H(4), H(5), H(6), H(7)} = {1,0,1,0}.
Since H(2) = 0 and H(3) = 1, let n = 1 and by using (1), ..., (8) of Lemma 3.4 we have
{H(8),H(9),H(10),H(11),H(12),H(13),H(14),H(15)} = {0,1,0,1,0,1,0,1}.
Since H(4) = 1 and H(5) = 0, let n = 2 and by using (1), ..., (8) of Lemma 3.4 we have {H(16),H(17),H(18),H(19),H(20),H(21),H(22),H(23)} = {1,0,1,0,1,0,1,0}. Since H(6) = 1 and H(7) = 0, let n = 3 and by using (1), ..., (8) of Lemma 3.4 we have
{H(24),H(25),H(26),H(27),H(28),H(29),H(30),H(31)} = {1,0,1,0,1,0,1,0}.
Therefore we can calculate the value of each H(n) in 3.7, and we get the following triangle of numbers.

 (3.8)

We can make a theorem by generalizing the pattern we found in Example 3.2.

Theorem 3.1 (1)   Suppose that then

(2) Suppose that then

Proof   Here we can use the method that is similar to the one used in Example 3.2. By Lemma 3.4 we can get the values of H(8n), H(8n+1), H(8n+2), H(8n+3), H(8n+4),H(8n+5), H(8n+6),H(8n+7) from the values of H(2n) and H(2n+1) for any natural number . In this way we can prove this theorem.

Example 3.3   Now we are going to show how the pattern in and Lemma 3.3 produce the pattern in .
By Lemma 3.3 is odd for any non-negative number .
By and we have
{H(2),H(4),H(6),H(8),H(10),H(12),H(14),H(16),H(18)}
= {0,1,1,0,0,0,0,1,1}, and hence by Lemma 3.3 we have
{JI(2),JI(4),JI(6),JI(8),JI(10),JI(12),JI(14),JI(16),JI(18) }
= {1,0,0,1,1,1,1,0,0}.
In this way we can calculate
by .

Theorem 3.2 (1)   Suppose that then

(2) Suppose that then
.

Proof   We can prove this theorem by the same method that we used in Example 3.3. By Lemma 3.3 is odd for any non-negative integer .
By Theorem 3.1 and Lemma 3.3 we can get the values of for any natural number .

Example 3.4   Figure (3.1) is the graph of the list {JI(n) , , 3, ..., 256} and Figure (3.2) is the graph of the list {JI(n) , , 3, ..., 1024}. The horizontal coordinate is for the number of numbers (or people in the original Josephus problem) involved in the game, and the vertical coordinate is the number that remains when the game is over. For example by we have the point in the graph.
.

Figure (3.1.)
Figure (3.2)
If we compare Figure 3.1 and 3.2, we can discover a very interesting fact. That is the existence of self-similarity. As to the research of self-similarity by the authors see .

Is there any relation between the patterns of the sequence {, n = 1,2,...} and the self-similarity of Figure (3.1) and Figure (3.2)?

Example 3.5   Here we present recursive relations that have nothing to do with the Josephus problem. First we let , and
(1) .
(2)
(3)
(4)
(5)
(6)
(7)
(8)
If we calculate for we get {1, 1, 3, 4, 3, 7, 1, 3, 9, 1, 11, 7, 11, 9, 9, 13, 5, 11, 7, 13, 11, 15, 9, 25, 1, 23, 3, 29, 3, 31, 1, 11, 25, 9, 27, 7, 35, 9, 33, 3, 41, 1, 43, 7, 43, 9, 41, 25, 25, 25, 27, 15, 43, 17, 41, 33, 25, 31, 27, 31, 35, 33, 33}. In these numbers 4 is the only even number. In fact this is the only even number in {, } by the calculation of the computer algebra system Mathematica.
Figure (3.3) is the graph of the list {F(n) , , 3, ..., 256} and Figure (3.4) is the graph of the list {F(n), , 3, ..., 1024}.

Figure (3.3.)
Figure (3.4)
The sequence {F(n) , n = 1,2,...} = {1,1,1,0,1,1,1,...} does not have any interesting pattern, but the graph of it has the self-similarity. By this example we know that a sequence can produce a graph with the self-similarity even if it does not have any interesting pattern when reduced by 2. Therefore the authors think it is almost sure that there is not any relation between the pattern of sequence in 3.2 and the graph that is produced by it.

Acknowledgments
Contributions from Hiroshi Matsui, Soh Tatsumi and Takahumi Inoue. Although they were not the primary authors, their contributions were significant. We would like to thank Mr. Harrison Gray for helping us to prepare this article.