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.


*      Josephus problem               10/02/2017
JOSEPH CSECT
       USING  JOSEPH,R13              base register
       B      72(R15)                 skip savearea
       DC     17F'0'                  savearea
       STM    R14,R12,12(R13)         prolog
       ST     R13,4(R15)              " <-
       ST     R15,8(R13)              " ->
       LR     R13,R15                 " addressability
       LA     R7,1                    m=1
       DO WHILE=(C,R7,LE,=A(NPROB))   do m=1 to nprob
         LR     R1,R7                   m
         MH     R1,=H'6'                *6
         LH     R2,PROB-6(R1)
         ST     R2,N                    n=prob(m,1)
         LH     R2,PROB-4(R1)
         ST     R2,W                    w=prob(m,2)
         LH     R2,PROB-2(R1)
         ST     R2,S                    s=prob(m,3)
         MVC    PG,=CL80'josephus'      init buffer
         L      R1,N                    n
         XDECO  R1,DEC                  edit
         MVC    PG+8(4),DEC+8           output
         L      R1,W                    w
         XDECO  R1,DEC                  edit 
         MVC    PG+12(4),DEC+8          output
         L      R1,S                    s
         XDECO  R1,DEC                  edit 
         MVC    PG+16(4),DEC+8          output
         XPRNT  PG,L'PG                 print buffer
         MVI    DEAD,X'00'              dead(1)='0'B;
         MVC    DEAD+1(255),DEAD        dead(*)='0'B;
         L      R11,N                   nx=n
         L      R8,=F'-1'               p=-1
         DO UNTIL=(C,R11,EQ,S)          do until n=s 
           SR     R9,R9                   found=0
           DO UNTIL=(C,R9,EQ,W)           do until found=w 
             LA     R8,1(R8)                p=p+1
             IF C,R8,EQ,N THEN              if p=nn then
               SR     R8,R8                   p=0
             ENDIF  ,                       end if
             LA     R2,DEAD(R8)             @dead(p+1)
             IF CLI,0(R2),EQ,X'00' THEN     if not dead(p+1) then
               LA     R9,1(R9)                found=found+1
             ENDIF  ,                       end if
           ENDDO  ,                       end do
           LA     R2,DEAD(R8)             @dead(p+1)
           MVI    0(R2),X'01'             dead(p+1)='1'B
           BCTR   R11,0                   nx=nx-1
         ENDDO  ,                       end do
         MVC    PG,=CL80' '             clear buffer
         LA     R10,PG                  ipg=0
         L      R9,N                    nn
         BCTR   R9,0                    nn-1
         SR     R6,R6                   i=0
         DO WHILE=(CR,R6,LE,R9)         do i=0 to nn-1
           LA     R2,DEAD(R6)             @dead(i+1)
           IF CLI,0(R2),EQ,X'00' THEN     if not dead(i+1) then
             XDECO  R6,DEC                  edit i
             MVC    0(4,R10),DEC+8          output
             LA     R10,4(R10)              ipg=ipg+4
           ENDIF  ,                       end if
           LA     R6,1(R6)                i=i+1
         ENDDO  ,                       end do
         XPRNT  PG,L'PG                 print buffer
         LA     R7,1(R7)                m=m+1
       ENDDO  ,                       end do
       L      R13,4(0,R13)            epilog 
       LM     R14,R12,12(R13)         " restore
       XR     R15,R15                 " rc=0
       BR     R14                     exit
PROB   DC     H'41',H'3',H'1'         round 1
       DC     H'41',H'3',H'3'         round 2
NPROB  EQU    (*-PROB)/6              number of rounds
N      DS     F                       n number of prisoners
W      DS     F                       w killing count
S      DS     F                       s number of prisoners to survive
PG     DS     CL80                    buffer
DEC    DS     CL12                    temp for xdeco
DEAD   DS     256X                    n max
       YREGS
       END    JOSEPH