Josephus problem is a math puzzle with a grim description: 



n


{\displaystyle n}

 prisoners are standing on a circle, sequentially numbered from 



0


{\displaystyle 0}

 to 



n
−
1


{\displaystyle n-1}

.

An executioner walks along the circle, starting from prisoner 



0


{\displaystyle 0}

,
removing every 



k


{\displaystyle k}

-th prisoner and killing him.

As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. >

For example, if there are 



n
=
5


{\displaystyle n=5}

 prisoners and 



k
=
2


{\displaystyle k=2}

, the order the prisoners are killed in (let's call it the "killing sequence") will be 1, 3, 0, and 4, and the survivor will be #2.



Task

Given any   



n
,
k
>
0


{\displaystyle n,k>0}

,   find out which prisoner will be the final survivor.

In one such incident, there were 41 prisoners and every 3rd prisoner was being killed   (



k
=
3


{\displaystyle k=3}

).

Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale.

Which number was he?



Extra

The captors may be especially kind and let 



m


{\displaystyle m}

 survivors free,

and Josephus might just have   



m
−
1


{\displaystyle m-1}

   friends to save.

Provide a way to calculate which prisoner is at any given position on the killing sequence.



Notes

 You can always play the executioner and follow the procedure exactly as described, walking around the circle, counting (and cutting off) heads along the way. This would yield the complete killing sequence and answer the above questions, with a complexity of probably 



O
(
k
n
)


{\displaystyle O(kn)}

. However, individually it takes no more than 



O
(
m
)


{\displaystyle O(m)}

 to find out which prisoner is the 



m


{\displaystyle m}

-th to die.
 If it's more convenient, you can number prisoners from   



1


{\displaystyle 1}

 to 



n


{\displaystyle n}

   instead.   If you choose to do so, please state it clearly.
 An alternative description has the people committing assisted suicide instead of being executed, and the last person simply walks away. These details are not relevant, at least not mathematically.


/* REXX **************************************************************
* 15.11.2012 Walter Pachl - my own solution
* 16.11.2012 Walter Pachl generalized n prisoners + w killing distance
*                         and s=number of survivors
* 09.05.2013 Walter Pachl accept arguments n w s and fix output
*                         thanks for the review/test
* I see no need for specifying a start count (actually a start number)
* This task states:      n    prisoners are standing on a circle, 
*    sequentially numbered from  0  to  n-1.    The 1st prisoner is  0. 
* This program should work on EVERY REXX. 
* Pls report if this is not the case and let us know what's a problem.
**********************************************************************/
Parse Arg n w s .
If n='?' Then Do
  Say 'Invoke the program with the following arguments:'
  Say 'n number of prisoners            (default 41)'
  Say 'w killing count                  (default  3)'
  Say 's number of prisoners to survive (default  1)'
  Exit
  End
If n='' Then n=41                      /* number of alive prisoners  */
If w='' Then w=3                       /* killing count              */
If s='' Then s=1                       /* nuber of survivors         */
dead.=0                                /* nobody's dead yet          */
nn=n                                   /* wrap around boundary       */
p=-1                                   /* start here                 */
killed=''                              /* output of killings         */
Do until n=s                           /* until one alive prisoner   */
  found=0                              /* start looking              */
  Do Until found=w                     /* until we have the third    */
    p=p+1                              /* next position              */
    If p=nn Then p=0                   /* wrap around                */
    If dead.p=0 Then                   /* a prisoner who is alive    */
      found=found+1                    /* increment found count      */
    End
  dead.p=1
  /*
  Say 'killing' p 'now'
  */
  n=n-1                                /* shoot the one on this pos. */
  killed=killed p                      /* add to output              */
  End                                  /* End of main loop           */
Say 'killed:'killed                    /* output killing sequence    */
s=''
Do i=0 To nn-1                            /* look for the surviving p's */
  If dead.i=0 Then s=s i               /* found one                  */
  End
Say 'Survivor(s):'s                    /* show                       */