The Josephus Problem in Both Directions

Masakazu Naito, Toshiyuki Yamauchi, Daisuke Minematsu, Ryohei Miyadera, Kwansei Gakuin

In this article we study the Josephus problem in both direction. In this variant of the Josephus problem two numbers are to be eliminated at the same time, but two processes of elimination go for different directions. Suppose that there are -numbers and every -th numbers are to be eliminated. We denote the number that remains by . At a glance this Josephus problem looks like a simple puzzle and nothing more than a good example for computer programming, but the sequence presents interesting self-similarity of graph and the self-similarity of the sequence when each term is divided by a certain number. We have presented the self-similarities of this Josephus problem in "The Self-Similarity of the Josephus problem and its Variants, Visual Mathematics Volume 11, No. 2, 2009", but we have not proved the existence of the self-similarity of the sequence. In this article we prove it using the recursive relations when .