The Josephus Problem

In computer science and mathemetics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. Such games are used to pick out a person from a group.

A drawing for the Josephus problem sequence for 500 people and skipping value of 6. The horizontal axis is the number of the person. The vertical axis (top to bottom) is time (the number of cycle). A live person is drawn as green, a dead one is drawn as black.

In the particular counting-out game that gives rise to the Josephus problem, a number of people are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem—given the number of people, starting point, direction, and number to be skipped—is to choose the position in the initial circle to avoid execution.

function setup(){
        var num = parseInt(document.getElementById('people').value);
  var people = [];
  var i;
  for(i=0; i<num; i++){
        people.push("Person " + (i+1));
  }
  step(people);
}

function step(people){

        var x = 0;
  var y = 1;
  var output = document.getElementById('output');
  output.innerHTML = "";

        while(people.length > 1){
        var p = document.createElement("P");
        p.innerHTML = people[x] + " kills " + people[y];
        output.appendChild(p);

        people.splice(y, 1);

        x = y;
        x = (people.length > x) ? x : 0;

        y = x+1;
        y = (people.length > y) ? y : 0;
  }

  var resultBottom = document.createElement("P");
  resultBottom.innerHTML = people[0] + " is the only one left.";
  output.appendChild(resultBottom);
  var resultTop = document.createElement("P");
  resultTop.innerHTML = "N = " + people[0];
  output.prepend(resultTop);
}