iconEuler Examples

Survivor of the Josephus Problem

The following problem is a famous exercise in programming. It is
called the Josephus problem.

There are n persons in a circle. We start with one person, and count
to k clockwise. This person is removed from the circle. The process is
continued with the next person, until there is only one left. Which
one is it?

We solve it first with a simulation. The following function steps k
times from i to the right (scipping zeros). Then it removes this
element, returning its position.
>function countAndRemove (i,k,v) ...
  loop 1 to k
    repeat
      i=i+1;
      if i>cols(v) then i=1; endif;
      until v[i];
    end;
  end;
  v[i]=0;
  return i;
endfunction
Test that.
>format(4,0); v=ones(1,10)
  1   1   1   1   1   1   1   1   1   1 
>i=0; loop 1 to 9; i=countAndRemove(i,7,v), v, end;
  7 
  1   1   1   1   1   1   0   1   1   1 
  4 
  1   1   1   0   1   1   0   1   1   1 
  2 
  1   0   1   0   1   1   0   1   1   1 
  1 
  0   0   1   0   1   1   0   1   1   1 
  3 
  0   0   0   0   1   1   0   1   1   1 
  6 
  0   0   0   0   1   0   0   1   1   1 
 10 
  0   0   0   0   1   0   0   1   1   0 
  5 
  0   0   0   0   0   0   0   1   1   0 
  8 
  0   0   0   0   0   0   0   0   1   0 
That looks okay.

Now we can write a function, which removes n-1 persons, and returns
the position of the survivor.
>function map determineSurvivor (k,n) ...
  v=ones(1,n);
  i=0;
  loop 1 to n-1;
    i=countAndRemove(i,k,v);
  end;
  return nonzeros(v)
endfunction
>determineSurvivor(7,10)
  9 
Due to the map feature, we can generate a table for step sizes k, and
total numbers n.
>determineSurvivor(1:10,(1:10)')
  1   1   1   1   1   1   1   1   1   1 
  2   1   2   1   2   1   2   1   2   1 
  3   3   2   2   1   1   3   3   2   2 
  4   1   1   2   2   3   2   3   3   4 
  5   3   4   1   2   4   4   1   2   4 
  6   5   1   5   1   4   5   3   5   2 
  7   7   4   2   6   3   5   4   7   5 
  8   1   7   6   3   1   4   4   8   7 
  9   3   1   1   8   7   2   3   8   8 
 10   5   4   5   3   3   9   1   7   8 
At that point, we notice, that we are not very efficient. We could
remove just one person, and then using the function for one less
person recursively.

We are not going to implement this here.

The Josephus problem is a bit more complicated, since it asks for the
position of the last two remaining persons. But we can write a
function for this too.
>function determineLastTwoSurvivors (k,n) ...
  v=ones(1,n);
  i=0;
  loop 1 to n-2;
    i=countAndRemove(i,k,v);
  end;
  return nonzeros(v)
endfunction
>shortformat; determineLastTwoSurvivors(3,40)
[ 13  28 ]

Examples Homepage