Skip to main content
5 of 6
added 1 character in body
kirma
  • 19.1k
  • 1
  • 55
  • 95

How to correct my code for solving the Josephus problem?

###Problem Description

Recently, I have been reading the book Schaum's Outline of Mathematica (2nd Edition), where I encounted the problem:

Flavius Josephus was a Jewish historian of the first century. He wrote about a group of ten Jews in a cave who, rather than surrender to the Romans, chose to commit suicide, one by one. They formed a circle and every other one was killed. Who was the lone survivor?

The author's solution:

list = Range[10];
While[Length[list] > 1, list = Rest[RotateLeft[list]]];
list

{5}

However, I know it is not efficient to use the procedural methods such as Do, While, etc. Rather, I want use a functional method like NestWhile, Nest, or FixedPoint to solve the problem.

My solutions:

Method 1:

list = Range @ 10; 
NestList[Rest@RotateLeft[#] &, list, 9]
 {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 
  {3, 4, 5, 6, 7, 8, 9, 10, 1}, 
  {5, 6, 7, 8, 9, 10, 1, 3}, 
  {7, 8, 9, 10, 1, 3, 5}, 
  {9, 10, 1, 3, 5, 7}, 
  {1, 3, 5, 7, 9}, 
  {5, 7, 9, 1}, 
  {9, 1, 5}, 
  {5, 9},
  {5}}

Furthermore,this method has a flaw that I must give the the number of iterations. In fact, sometimes that is unknown.

Method 2:

list = Range @10;
FixedPoint[If[Length@# != 1 &, Rest @ RotateLeft[#] &], list]

Unfortunately, method 2 doesn't work.

Method 3:

 list = Range @ 10;
 NestWhileList[Rest @ RotateLeft[#] &, list, Length@list != 1]
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

So my question is: what is a good way to do it?

xyz
  • 655
  • 4
  • 38
  • 117