Josephus problem

From Rosetta Code
Task
Josephus problem
You are encouraged to solve this task according to the task description, using any language you may know.

Josephus problem is a math puzzle with a grim description: prisoners are standing on a circle, sequentially numbered from to .

An executioner walks along the circle, starting from prisoner , removing every -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 prisoners and , 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   ,   find out which prisoner will be the final survivor.

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

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 survivors free,
and Josephus might just have     friends to save.

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


Notes
  1. 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 . However, individually it takes no more than to find out which prisoner is the -th to die.
  2. If it's more convenient, you can number prisoners from   to   instead.   If you choose to do so, please state it clearly.
  3. 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.



11l[edit]

Translation of: Python
F j(n, k)
   V p = Array(0 .< n)
   V i = 0
   [Int] seq
   L !p.empty
      i = (i + k - 1) % p.len
      seq.append(p.pop(i))
   R "Prisoner killing order: #..\nSurvivor: #.".format(seq[0 .< (len)-1].join(‘, ’), seq.last)

print(j(5, 2))
print(j(41, 3))
Output:
Prisoner killing order: 1, 3, 0, 4.
Survivor: 2
Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15.
Survivor: 30

360 Assembly[edit]

Translation of: REXX

The program uses two ASSIST macros (XDECO,XPRNT) to keep the code as short as possible.

*      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
Output:
josephus  41   3   1
  30
josephus  41   3   3
  15  30  34

6502 Assembly[edit]

This subroutine expects to be called with the value of n in the accumulator and the value of k in index register X. It returns with the index of the survivor in the accumulator, and also leaves an array beginning at address 1000 hex giving the order in which the prisoners died. For example, in the case where n = 5 and k = 2, the values stored in the array are 2, 0, 4, 1, 3. From this we see that prisoner 1 was the first to die, then prisoner 3, and so on. (Note that prisoner 2 in this instance is the survivor.)

JSEPHS: STA  $D0        ; n
        STX  $D1        ; k
        LDA  #$FF
        LDX  #$00
SETUP:  STA  $1000,X    ; populate array with hex FF
        INX
        CPX  $D0
        BEQ  KILL
        JMP  SETUP
KILL:   LDA  #$00       ; number killed so far
        STA  $D2
        LDX  #$00       ; position within array
        LDY  #$01       ; counting up to k
FIND:   INY
SCAN:   INX
        CPX  $D0
        BMI  TEST
        LDX  #$00       ; circle back around
TEST:   LDA  $1000,X
        CMP  #$FF
        BNE  SCAN       ; already been killed
        CPY  $D1
        BMI  FIND       ; if y < k keep going round
        LDA  $D2
        STA  $1000,X    ; mark as dead
        CLC
        ADC  #$01
        STA  $D2
        CMP  $D0        ; have we killed all but 1?
        BPL  RETURN
        LDY  #$00
        JMP  FIND
RETURN: TXA             ; a <- index of survivor
        RTS

AArch64 Assembly[edit]

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program josephus64.s   */
/* run with josephus64 maxi intervalle */
/* example : josephus64 41 3

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

.equ FIRSTNODE,        0              //identification first node 

/*******************************************/
/* Structures                               */
/********************************************/
/* structure linkedlist*/
    .struct  0
llist_next:                            // next element
    .struct  llist_next + 8
llist_value:                           // element value
    .struct  llist_value + 8
llist_fin:
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessDebutPgm:          .asciz "Start program.\n"
szMessFinPgm:            .asciz "Program End ok.\n"
szRetourLigne:            .asciz "\n"
szMessValElement:        .asciz "Value : @ \n"
szMessListeVide:         .asciz "List empty.\n"
szMessImpElement:        .asciz "Node display: @ Value : @ Next @ \n"
szMessErrComm:           .asciz "Incomplete Command line  : josephus64 <maxi> <intervalle>\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
sZoneConv:         .skip 100
.align 4
qDebutListe1:       .skip llist_fin
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                   // entry of program 
    mov fp,sp                           // copy stack address  register x29 fp
    ldr x0,qAdrszMessDebutPgm
    bl affichageMess
    ldr x0,[fp]                         // parameter number command line
    cmp x0,#2                           // correct ?
    ble erreurCommande                  // error

    add x0,fp,#16                       // address parameter 2
    ldr x0,[x0]
    bl conversionAtoD
    add x22,x0,FIRSTNODE                // save maxi
    add x0,fp,#24                       // address parameter 3
    ldr x0,[x0]
    bl conversionAtoD
    mov x21,x0                          // save gap

    mov x0,FIRSTNODE                    // create first node
    mov x1,0
    bl createNode
    mov x25,x0                          // first node address
    mov x26,x0
    mov x24,FIRSTNODE + 1
    mov x23,1
1:                                      // loop create others nodes
    mov x0,x24                          // key value
    mov x1,0
    bl createNode
    str x0,[x26,llist_next]             // store current node address in prev node
    mov x26,x0
    add x24,x24,1
    add x23,x23,1
    cmp x23,x22                         // maxi ?
    blt 1b
    str x25,[x26,llist_next]            // store first node address in last pointer
    mov x24,x26
2:
    mov x20,1                           // counter for gap
3:
    ldr x24,[x24,llist_next]
    add x20,x20,1
    cmp x20,x21                         // intervalle ?
    blt 3b
    ldr x25,[x24,llist_next]            // removing the node from the list
    ldr x22,[x25,llist_value]
    ldr x27,[x25,llist_next]            // load pointer next
    str x27,[x24,llist_next]            // ans store in prev node
    //mov x0,x25
    //bl displayNode
    cmp x27,x24
    csel x24,x24,x27,ne                 // next node address 
    bne 2b                              // and loop
 
    mov x0,x24
    bl displayNode                      // display last node

    b 100f
erreurCommande:
    ldr x0,qAdrszMessErrComm
    bl affichageMess
    mov x0,#1                          // error code
    b 100f
100:                                   // program end standard 
    ldr x0,qAdrszMessFinPgm
    bl affichageMess
    mov x0,0                          // return code Ok
    mov x8,EXIT                       // system call "Exit"
    svc #0

qAdrszMessDebutPgm:      .quad szMessDebutPgm
qAdrszMessFinPgm:        .quad szMessFinPgm
qAdrszRetourLigne:       .quad szRetourLigne
qAdrqDebutListe1:        .quad qDebutListe1
qAdrszMessErrComm:       .quad szMessErrComm

/******************************************************************/
/*     create node                                             */ 
/******************************************************************/
/* x0 contains key   */
/* x1 contains zero or address next node */
/* x0 returns address heap node  */
createNode:
    stp x20,lr,[sp,-16]!        // save  registres
    stp x21,x22,[sp,-16]!       // save  registres
    mov x20,x0                  // save key
    mov x21,x1                  // save key
    mov x0,#0                   // allocation place heap
    mov x8,BRK                  // call system 'brk'
    svc #0
    mov x22,x0                  // save address heap for node
    add x0,x0,llist_fin         // reservation place node length
    mov x8,BRK                  // call system 'brk'
    svc #0
    cmp x0,#-1                  // allocation error
    beq 100f

    str x20,[x22,llist_value]
    str x21,[x22,llist_next]
    mov x0,x22
100:
    ldp x21,x22,[sp],16         // restaur des  2 registres
    ldp x20,lr,[sp],16          // restaur des  2 registres
    ret                         // retour adresse lr x30

/******************************************************************/
/*     display infos node                                     */ 
/******************************************************************/
/* x0 contains node address */
displayNode:
    stp x1,lr,[sp,-16]!        // save  registres
    stp x2,x3,[sp,-16]!        // save  registres
    mov x2,x0
    ldr x1,qAdrsZoneConv
    bl conversion16
    ldr x0,qAdrszMessImpElement
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc
    mov x3,x0
    ldr x0,[x2,llist_value]
    ldr x1,qAdrsZoneConv
    bl conversion10S
    mov x0,x3
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc
    mov x3,x0
    ldr x0,[x2,llist_next]
    ldr x1,qAdrsZoneConv
    bl conversion16
    mov x0,x3
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc
    bl affichageMess

100:
    ldp x2,x3,[sp],16          // restaur des  2 registres
    ldp x1,lr,[sp],16          // restaur des  2 registres
    ret                        // retour adresse lr x30
qAdrsZoneConv:               .quad sZoneConv
qAdrszMessImpElement:        .quad szMessImpElement
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Output:
pi@debian-buster-64:~/asm64/rosetta/asm5 $ josephus64 41 3
Start program.
Node display: 000000000FFCB1E0 Value : +30 Next 000000000FFCB1E0
Program End ok.
pi@debian-buster-64:~/asm64/rosetta/asm5 $ josephus64 5 2
Start program.
Node display: 000000002BDF7020 Value : +2 Next 000000002BDF7020
Program End ok.

Ada[edit]

The procedure reads up to 4 parameters from the command line: the number N of prisoners, the step size K, the number M of survivors, and an indicator whether the executions shall be printed ("1") or only surviving prisoners (any other input). The defaults are 41, 3, 1, 1. The prison cells are numbered from 0 to N-1.

with Ada.Command_Line, Ada.Text_IO;

procedure Josephus is

   function Arg(Idx, Default: Positive) return Positive is -- read Argument(Idx)
      (if Ada.Command_Line.Argument_Count >= Index
         then Positive'Value(Ada.Command_Line.Argument(Index)) else Default);

   Prisoners:  constant Positive := Arg(Idx => 1, Default => 41);
   Steps:      constant Positive := Arg(Idx => 2, Default =>  3);
   Survivors:  constant Positive := Arg(Idx => 3, Default =>  1);
   Print:               Boolean := (Arg(Idx => 4, Default =>  1) = 1);

   subtype Index_Type is Natural range 0 .. Prisoners-1;
   Next: array(Index_Type) of Index_Type;
   X: Index_Type := (Steps-2) mod Prisoners;

begin
   Ada.Text_IO.Put_Line
     ("N =" & Positive'Image(Prisoners) & ",  K =" & Positive'Image(Steps) &
        (if Survivors > 1 then ",  #survivors =" & Positive'Image(Survivors)
        else ""));
   for Idx in Next'Range loop -- initialize Next
      Next(Idx) := (Idx+1) mod Prisoners;
   end loop;
   if Print then
      Ada.Text_IO.Put("Executed: ");
   end if;
   for Execution in reverse 1 .. Prisoners loop
      if Execution = Survivors then
         Ada.Text_IO.New_Line;
         Ada.Text_IO.Put("Surviving: ");
         Print := True;
      end if;
      if Print then
         Ada.Text_IO.Put(Positive'Image(Next(X)));
      end if;
      Next(X) := Next(Next(X)); -- "delete" a prisoner
      for Prisoner in 1 .. Steps-1 loop
         X := Next(X);
      end loop;
   end loop;
end Josephus;
Output:
$ ./josephus
N = 41,  K = 3
Executed:  2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Surviving:  30

$ ./josephus 23482 3343 3 0
N = 23482,  K = 3343,  #survivors = 3

Surviving:  13317 1087 1335

ALGOL 68[edit]

Translated from the C

BEGIN
   PROC josephus = (INT n, k, m) INT :
   CO Return m-th on the reversed kill list; m=0 is final survivor. CO
   BEGIN
      INT lm := m;			CO Local copy of m CO
      FOR a FROM m+1 WHILE a <= n DO lm := (lm+k) %* a OD;
      lm
   END;
   INT n = 41, k=3;
   printf (($"n = ", g(0), ", k = ", g(0), ", final survivor: ", g(0)l$,
	    n, k, josephus (n, k, 0)))
END
Output:
n = 41, k = 3, final survivor: 30

ANSI Standard BASIC[edit]

Translated from ALGOL 68

100 FUNCTION josephus (n, k, m)
110 ! Return m-th on the reversed kill list; m=0 is final survivor.
120    LET lm = m  ! Local copy OF m
130    FOR a = m+1  TO n 
140       LET lm = MOD(lm+k, a) 
150    NEXT a
160    LET josephus = lm
170 END FUNCTION
180 LET n = 41
190 LET k=3
200 PRINT "n =";n, "k =";k,"final survivor =";josephus(n, k, 0)
210 END

AppleScript[edit]

Straightforward[edit]

Both scripts here use 1-based numbering.

Translation of: BBC BASIC
on josephus(n, k)
    set m to 0
    repeat with i from 2 to n
        set m to (m + k) mod i
    end repeat
    
    return m + 1
end josephus

josephus(41, 3) --> 31

Or with an option to specify the number of survivors:

on josephus(n, k, s)
    script o
        property living : {}
    end script
    
    repeat with i from 1 to n
        set end of o's living to i
    end repeat
    
    set startPosition to k
    repeat until (n = s) -- Keep going round the circle until only s prisoners remain.
        set circleSize to n
        if (n < k) then
            set i to (startPosition - 1) mod circleSize + 1
            set item i of o's living to missing value
            set n to n - 1
        else
            repeat with i from startPosition to circleSize by k
                set item i of o's living to missing value
                set n to n - 1
                if (n = s) then exit repeat
            end repeat
        end if
        set startPosition to i + k - circleSize
        set o's living to o's living's integers
    end repeat
    
    return o's living
end josephus

josephus(41, 3, 1) --> {31}
josephus(41, 3, 6) --> {2, 4, 16, 22, 31, 35}

Composition of pure functions[edit]

Composing a solution from generic and reusable (pure) functions, and using the zero-based notation of the problem statement:

-- josephusSurvivor :: Int -> Int -> Int
on josephusSurvivor(n, k)
    script go
        on |λ|(x, a)
            (k + x) mod a
        end |λ|
    end script
    
    foldl(go, 0, enumFromTo(1, n))
end josephusSurvivor


-- josephusSequence :: Int -> Int -> [Int]
on josephusSequence(n, k)
    script josephus
        on |λ|(m, xs)
            if 0  m then
                set {l, r} to splitAt((k - 1) mod m, xs)
                {item 1 of r} & |λ|(m - 1, rest of r & l)
            else
                {}
            end if
        end |λ|
    end script
    
    |λ|(n, enumFromTo(0, n - 1)) of josephus
end josephusSequence


--------------------------- TEST ---------------------------
on run
    unlines({"Josephus survivor -> " & str(josephusSurvivor(41, 3)), ¬
        "Josephus sequence ->" & linefeed & tab & ¬
        showList(josephusSequence(41, 3))})
end run


---------------- REUSABLE GENERIC FUNCTIONS ----------------

-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
    if m  n then
        set lst to {}
        repeat with i from m to n
            set end of lst to i
        end repeat
        lst
    else
        {}
    end if
end enumFromTo

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    -- The list obtained by applying f
    -- to each element of xs.
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    -- 2nd class handler function lifted into 1st class script wrapper. 
    if script is class of f then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, delim}
    set str to xs as text
    set my text item delimiters to dlm
    str
end intercalate

-- showList :: [a] -> String
on showList(xs)
    script show
        on |λ|(x)
            x as text
        end |λ|
    end script
    "[" & intercalate(",", map(show, xs)) & "]"
end showList

-- splitAt :: Int -> [a] -> ([a], [a])
on splitAt(n, xs)
    if n > 0 and n < length of xs then
        if class of xs is text then
            {items 1 thru n of xs as text, ¬
                items (n + 1) thru -1 of xs as text}
        else
            {items 1 thru n of xs, items (n + 1) thru -1 of xs}
        end if
    else
        if n < 1 then
            {{}, xs}
        else
            {xs, {}}
        end if
    end if
end splitAt

-- str :: a -> String
on str(x)
    x as string
end str

-- unlines :: [String] -> String
on unlines(xs)
    -- A single string formed by the intercalation
    -- of a list of strings with the newline character.
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, linefeed}
    set str to xs as text
    set my text item delimiters to dlm
    str
end unlines
Output:
Josephus survivor -> 30
Josephus sequence ->
    [2,5,8,11,14,17,20,23,26,29,32,35,38,0,4,9,13,18,22,27,31,36,40,6,12,19,25,33,39,7,16,28,37,10,24,1,21,3,34,15,30]

ARM Assembly[edit]

Works with: as version Raspberry Pi
/* ARM assembly AARCH64 Raspberry PI 3B */
/* ARM assembly Raspberry PI  */
/*  program josephus.s   */

/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */

/*******************************************/
/* Constantes                              */
/*******************************************/
.equ STDOUT, 1           @ Linux output console
.equ EXIT,   1           @ Linux syscall
.equ WRITE,  4           @ Linux syscall
.equ BRK,    0x2d        @ Linux syscall
.equ CHARPOS,     '@'

.equ FIRSTNODE,        0              //identification first node 

/*******************************************/
/* Structures                               */
/********************************************/
/* structure linkedlist*/
    .struct  0
llist_next:                            // next element
    .struct  llist_next + 4
llist_value:                           // element value
    .struct  llist_value + 4
llist_fin:
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessDebutPgm:          .asciz "Start program.\n"
szMessFinPgm:            .asciz "Program End ok.\n"
szRetourLigne:            .asciz "\n"
szMessValElement:        .asciz "Value : @ \n"
szMessListeVide:         .asciz "List empty.\n"
szMessImpElement:        .asciz "Node display: @ Value : @ Next @ \n"
szMessErrComm:           .asciz "Incomplete Command line  : josephus <maxi> <intervalle>\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
sZoneConv:         .skip 24
.align 4
qDebutListe1:      .skip llist_fin
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                   // entry of program 
    mov fp,sp                           // copy stack address  register r29 fp
    ldr r0,iAdrszMessDebutPgm
    bl affichageMess
    ldr r0,[fp]                        // parameter number command line
    cmp r0,#2                          // correct ?
    ble erreurCommande                 // error

    add r0,fp,#8                       // address parameter 2
    ldr r0,[r0]
    bl conversionAtoD
    add r2,r0,#FIRSTNODE               // save maxi
    add r0,fp,#12                      // address parameter 3
    ldr r0,[r0]
    bl conversionAtoD
    mov r8,r0                          // save gap

    mov r0,#FIRSTNODE                  // create first node
    mov r1,#0
    bl createNode
    mov r5,r0                          // first node address
    mov r6,r0
    mov r4,#FIRSTNODE + 1
    mov r3,#1
1:                                     // loop create others nodes
    mov r0,r4                          // key value
    mov r1,#0
    bl createNode
    str r0,[r6,#llist_next]             // store current node address in prev node
    mov r6,r0
    add r4,r4,#1
    add r3,r3,#1
    cmp r3,r2                          // maxi ?
    blt 1b
    str r5,[r6,#llist_next]            // store first node address in last pointer
    mov r4,r6
2:
    mov r2,#1                          // counter for gap
3:
    ldr r4,[r4,#llist_next]
    add r2,r2,#1
    cmp r2,r8                          // intervalle ?
    blt 3b
    ldr r5,[r4,#llist_next]            // removing the node from the list
    ldr r2,[r5,#llist_value]
    ldr r7,[r5,#llist_next]            // load pointer next
    str r7,[r4,#llist_next]            // ans store in prev node
    //mov r0,r25
    //bl displayNode
    cmp r7,r4
    moveq r4,r7
    bne 2b                              // and loop
 
    mov r0,r4
    bl displayNode                      // display last node

    b 100f
erreurCommande:
    ldr r0,iAdrszMessErrComm
    bl affichageMess
    mov r0,#1                          // error code
    b 100f
100:                                   // program end standard 
    ldr r0,iAdrszMessFinPgm
    bl affichageMess
    mov r0,#0                          // return code Ok
    mov r7,#EXIT                       // system call "Exit"
    svc #0

iAdrszMessDebutPgm:      .int szMessDebutPgm
iAdrszMessFinPgm:        .int szMessFinPgm
iAdrszRetourLigne:       .int szRetourLigne
iAdrqDebutListe1:        .int qDebutListe1
iAdrszMessErrComm:       .int szMessErrComm

/******************************************************************/
/*     create node                                             */ 
/******************************************************************/
/* r0 contains key   */
/* r1 contains zero or address next node */
/* r0 returns address heap node  */
createNode:
    push {r1-r11,lr}            // save  registers 
    mov r9,r0                   // save key
    mov r10,r1                  // save key
    mov r0,#0                   // allocation place heap
    mov r7,#BRK                 // call system 'brk'
    svc #0
    mov r11,r0                  // save address heap for node
    add r0,r0,#llist_fin        // reservation place node length
    mov r7,#BRK                 // call system 'brk'
    svc #0
    cmp r0,#-1                  // allocation error
    beq 100f

    str r9,[r11,#llist_value]
    str r10,[r11,#llist_next]
    mov r0,r11
100:
    pop {r1-r11,lr}            // restaur registers
    bx lr                      // return

/******************************************************************/
/*     display infos node                                     */ 
/******************************************************************/
/* r0 contains node address */
displayNode:
    push {r1-r4,lr}           // save  registers 
    mov r2,r0
    ldr r1,iAdrsZoneConv
    bl conversion16
    mov r4,#0
    strb r4,[r1,r0]           // store zero final
    ldr r0,iAdrszMessImpElement
    ldr r1,iAdrsZoneConv
    bl strInsertAtCharInc
    mov r3,r0
    ldr r0,[r2,#llist_value]
    ldr r1,iAdrsZoneConv
    bl conversion10S
    mov r4,#0
    strb r4,[r1,r0]           // store zero final
    mov r0,r3
    ldr r1,iAdrsZoneConv
    bl strInsertAtCharInc
    mov r3,r0
    ldr r0,[r2,#llist_next]
    ldr r1,iAdrsZoneConv
    bl conversion16
    mov r4,#0
    strb r4,[r1,#8]           // store zero final
    mov r0,r3
    ldr r1,iAdrsZoneConv
    bl strInsertAtCharInc
    bl affichageMess

100:
    pop {r1-r4,lr}            // restaur registers
    bx lr                     // return
iAdrsZoneConv:               .int sZoneConv
iAdrszMessImpElement:        .int szMessImpElement
/***************************************************/
/*      ROUTINES INCLUDE                 */
/***************************************************/
.include "../affichage.inc"
pi@raspberrypi:~/asm32/rosetta32/ass6 $ josephus 41 3
Start program.
Node display: 00F880F0 Value :         +30 Next 00F880F0
Program End ok.

Arturo[edit]

josephus: function [n,k][
    p: new 0..n-1
    i: 0
    seq: []

    while [0 < size p][
        i: (i+k-1) % size p
        append 'seq p\[i]
        remove 'p .index i
    ]
    print ["Prisoner killing order:" chop seq]
    print ["Survivor:" last seq]
    print ""
]

print "josephus 5 2 =>" 
josephus 5 2

print "josephus 41 3 =>"
josephus 41 3
Output:
josephus 5 2 =>
Prisoner killing order: [1 3 0 4] 
Survivor: 2 

josephus 41 3 =>
Prisoner killing order: [2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15] 
Survivor: 30

AutoHotkey[edit]

; Since AutoHotkey is 1-based, we're numbering prisoners 1-41.
nPrisoners := 41
kth        := 3

; Build a list, purposefully ending with a separator
Loop % nPrisoners
	list .= A_Index . "|"

; iterate and remove from list
i := 1
Loop
{
	; Step by 2; the third step was done by removing the previous prisoner
	i += kth - 1
	if (i > nPrisoners)
		i := Mod(i, nPrisoners)
	; Remove from list
	end := InStr(list, "|", 0, 1, i)
	bgn := InStr(list, "|", 0, 1, i-1)
	list := SubStr(list, 1, bgn) . SubStr(list, end+1)
	nPrisoners--
}
Until (nPrisoners = 1)
MsgBox % RegExReplace(list, "\|") ; remove the final separator
Output:
31

Note that since this is one-based, the answer is correct, though it differs with many other examples.

Using Objects[edit]

nPrisoners := 41
kth        := 3
list       := []

; Build a list of 41 items
Loop % nPrisoners
	list.insert(A_Index)

; iterate and remove from list
i := 1
Loop
{
	; Step by 3
	i += kth - 1
	if (i > list.MaxIndex())
		i := Mod(i, list.MaxIndex())
	list.remove(i)
}
Until (list.MaxIndex() = 1)
MsgBox % list.1 ; there is only 1 element left

AWK[edit]

# syntax: GAWK -f JOSEPHUS_PROBLEM.AWK
# converted from PL/I
BEGIN {
    main(5,2,1)
    main(41,3,1)
    main(41,3,3)
    exit(0)
}
function main(n,k,s,  dead,errors,found,i,killed,nn,p,survived) {
# n - number of prisoners
# k - kill every k'th prisoner
# s - number of survivors
    printf("\nn=%d k=%d s=%d\n",n,k,s) # show arguments
    if (s > n) { print("s>n"); errors++ }
    if (k <= 0) { print("k<=0"); errors++ }
    if (errors > 0) { return(0) }
    nn = n                             # wrap around boundary
    p = -1                             # start here
    while (n != s) {                   # until survivor count is met
      found = 0                        # start looking
      while (found != k) {             # until we have the k-th prisoner
        if (++p == nn) { p = 0 }       # wrap around
        if (dead[p] != 1) { found++ }  # if prisoner is alive increment found
      }
      dead[p] = 1                      # kill the unlucky one
      killed = killed p " "            # build killed list
      n--                              # reduce size of circle
    }
    for (i=0; i<=nn-1; i++) {
      if (dead[i] != 1) {
        survived = survived i " "      # build survivor list
      }
    }
    printf("killed: %s\n",killed)
    printf("survived: %s\n",survived)
    return(1)
}
Output:
n=5 k=2 s=1
killed: 1 3 0 4
survived: 2

n=41 k=3 s=1
killed: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
survived: 30

n=41 k=3 s=3
killed: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3
survived: 15 30 34

BASIC[edit]

Unstructured implementation: see solutions listed under specific BASIC dialects for structured versions.

10 N=41
20 K=3
30 M=0
40 FOR I=M+1 TO N
50 M=INT(I*((M+K)/I-INT((M+K)/I))+0.5)
60 NEXT I
70 PRINT "Survivor is number";M
Output:
Survivor is number 30

Applesoft BASIC[edit]

Translated from the BASIC implementation above and the ANSI Standard BASIC.

 10  DEF  FN MOD(X) = X - INT (X / A) * A
 20  LM = 0: INPUT "GIVE N AND K (N,K): ";N,K
 30  IF N < 1 or K < 1 THEN GOTO 20
 40  FOR A = 1 TO N: LM =  FN MOD(LM + K): NEXT A
 50  PRINT "N = ";N;", K = ";K;", SURVIVOR: ";LM
Output:
GIVE N AND K (N,K): 41,3
N = 41, K = 3, SURVIVOR: 30

IS-BASIC[edit]

100 PROGRAM "Josephus.bas"
110 INPUT PROMPT "Number of prisoners: ":NP
120 INPUT PROMPT "Execution step: ":EX
130 INPUT PROMPT "How many survivors:  ":SU
140 PRINT "Survivors:";
150 FOR S=0 TO SU-1
160   PRINT JOSEPHUS(NP,EX,S);
170 NEXT
180 DEF JOSEPHUS(N,K,M)
190   FOR I=M+1 TO N
200     LET M=MOD((M+K),I)
210   NEXT 
220   LET JOSEPHUS=M
230 END DEF

Batch File[edit]

Uses C's jos() function.

Translation of: C
@echo off
setlocal enabledelayedexpansion

set "prison=41"		%== Number of prisoners ==%
set "step=3"		%== The step... ==%
set "survive=1"		%== Number of survivors ==%
call :josephus

set "prison=41"
set "step=3"
set "survive=3"
call :josephus
pause
exit /b 0

	%== The Procedure ==%
:josephus
set "surv_list="
for /l %%S in (!survive!,-1,1) do (
	set /a "m = %%S - 1"
	for /l %%X in (%%S,1,!prison!) do (
		set /a "m = (m + step) %% %%X"
	)
	if defined surv_list (
		set "surv_list=!surv_list! !m!"
	) else (
		set "surv_list=!m!"
	)
)
echo !surv_list!
goto :EOF
Output:
30
34 15 30
Press any key to continue . . .

BBC BASIC[edit]

REM >josephus
PRINT "Survivor is number "; FNjosephus(41, 3, 0)
END
:
DEF FNjosephus(n%, k%, m%)
LOCAL i%
FOR i% = m% + 1 TO n%
  m% = (m% + k%) MOD i%
NEXT
= m%
Output:
Survivor is number 30

Befunge[edit]

The number of prisoners and step size are read from stdin.

>0" :srenosirP">:#,_&>>00p>>v
v0p01<&_,#!>#:<"Step size: "<
>1+:20p00g`!#v_0"  :rovivru"v
^g02%g02+g01<<@.$_,#!>#:<"S"<
Output:
Prisoners: 41
Step size: 3
Survivor:  30

C[edit]

#include <stdio.h>

// m-th on the reversed kill list; m = 0 is final survivor
int jos(int n, int k, int m) {
	int a;
	for (a = m + 1; a <= n; a++)
		m = (m + k) % a;
	return m;
}

typedef unsigned long long xint;

// same as jos(), useful if n is large and k is not
xint jos_large(xint n, xint k, xint m) {
	if (k <= 1) return n - m - 1;

	xint a = m;
	while (a < n) {
		xint q = (a - m + k - 2) / (k - 1);

		if (a + q > n)	q = n - a;
		else if (!q)	q = 1;

		m = (m + q * k) % (a += q);
	}

	return m;
}

int main(void) {
	xint n, k, i;

	n = 41;
	k = 3;
	printf("n = %llu, k = %llu, final survivor: %d\n", n, k, jos(n, k, 0));

	n = 9876543210987654321ULL;
	k = 12031;
	printf("n = %llu, k = %llu, three survivors:", n, k);

	for (i = 3; i--; )
		printf(" %llu", jos_large(n, k, i));
	putchar('\n');

	return 0;
}
Output:
n = 41, k = 3, final survivor: 30
n = 9876543210987654321, k = 12031, three survivors: 6892710366467541051 1946357796579138992 3554846299321782413

C#[edit]

namespace Josephus
{
    using System;
    using System.Collections;
    using System.Collections.Generic;

    public class Program
    {
        public static int[] JosephusProblem(int n, int m)
        {
            var circle = new List<int>();
            var order = new int[n];

            for (var i = 0; i < n; ++i)
            {
                circle.Add(i);
            }

            var l = 0;
            var j = 0;
            var k = 0;

            while (circle.Count != 0)
            {
                j++;
                if (j == m)
                {
                    order[k] = circle[l];
                    circle.RemoveAt(l);

                    k++;
                    l--;
                    j = 0;
                }

                if (k == n - 1)
                {
                    order[k] = circle[0];
                    circle.RemoveAt(0);
                }

                if (l == circle.Count - 1)
                {
                    l = 0;
                }
                else
                {
                    l++;
                }
            }

            return order;
        }

        static void Main(string[] args)
        {
            try
            {
                var n = 7;
                var m = 2;

                var result = JosephusProblem(n, m);

               for (var i = 0; i < result.Length; i++)
               {
                   Console.WriteLine(result[i]);//1 3 5 0 4 2 6
               }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }
            finally
            {
                Console.ReadLine();
            }
        }

    }
}

C++[edit]

#include <iostream>
#include <vector>

//--------------------------------------------------------------------------------------------------
using namespace std;
typedef unsigned long long bigint;

//--------------------------------------------------------------------------------------------------
class josephus
{
public:
    bigint findSurvivors( bigint n, bigint k, bigint s = 0 )
    {
	bigint i = s + 1;
	for( bigint x = i; x <= n; x++, i++ )
	    s = ( s + k ) % i;

	return s;
    }

    void getExecutionList( bigint n, bigint k, bigint s = 1 )
    {
	cout << endl << endl << "Execution list: " << endl;

	prisoners.clear();
	for( bigint x = 0; x < n; x++ )
	    prisoners.push_back( x );

	bigint index = 0;
	while( prisoners.size() > s )
	{
	    index += k - 1;
	    if( index >= prisoners.size() ) index %= prisoners.size();
	    cout << prisoners[static_cast<unsigned int>( index )] << ", ";

	    vector<bigint>::iterator it = prisoners.begin() + static_cast<unsigned int>( index );
	    prisoners.erase( it );
	}
    }

private:
    vector<bigint> prisoners;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
    josephus jo;
    bigint n, k, s;
    while( true )
    {
	system( "cls" );
	cout << "Number of prisoners( 0 to QUIT ): "; cin >> n;
	if( !n ) return 0;
	cout << "Execution step: "; cin >> k;
	cout << "How many survivors: "; cin >> s;
		
	cout << endl << "Survivor";
	if( s == 1 )
	{
	    cout << ": " << jo.findSurvivors( n, k );
	    jo.getExecutionList( n, k );
	}
	else
	{
	    cout << "s: ";
	    for( bigint x = 0; x < s; x++ )
		cout << jo.findSurvivors( n, k, x ) << ", ";

	    jo.getExecutionList( n, k, s );
	}

	cout << endl << endl;
	system( "pause" );
    }
    return 0;
}
//--------------------------------------------------------------------------------------------------
Output:
Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 1

Survivor: 30

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15,


Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 3

Survivors: 30, 15, 34,

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3,


Number of prisoners( 0 to QUIT ): 71
Execution step: 47
How many survivors: 11

Survivors: 29, 58, 41, 14, 39, 28, 35, 45, 64, 49, 27,

Execution list:
46, 22, 70, 48, 26, 5, 56, 36, 17, 0, 54, 38, 23, 9, 66, 55, 43, 33, 25, 16, 11,
6, 2, 69, 68, 1, 4, 10, 15, 24, 32, 42, 53, 65, 20, 40, 60, 19, 47, 8, 44, 13,
52, 31, 12, 62, 57, 50, 51, 61, 7, 30, 59, 34, 18, 3, 21, 37, 67, 63,

Clojure[edit]

(defn rotate [n s] (lazy-cat (drop n s) (take n s)))

(defn josephus [n k] 
   (letfn [(survivor [[ h & r :as l] k]
             (cond (empty? r) h
                   :else      (survivor (rest (rotate (dec k) l)) k)))]
     (survivor (range n) k)))

(let [n 41 k 3]
   (println (str "Given " n " prisoners in a circle numbered 1.." n 
                 ", an executioner moving around the"))
   (println (str "circle " k " at a time will leave prisoner number " 
                 (inc (josephus n k)) " as the last survivor.")))
Output:
Given 41 prisoners in a circle numbered 1..41, an executioner moving around the
circle 3 at a time will leave prisoner number 31 as the last survivor.

Common Lisp[edit]

Using a loop:

(defun kill (n k &aux (m 0))
  (loop for a from (1+ m) upto n do
        (setf m (mod (+ m k) a)))
  m)

Using a circular list.

(defun make-circular-list (n)
  (let* ((list (loop for i below n
                     collect i))
         (last (last list)))
    (setf (cdr last) list)
    list))

(defun kill (n d)
  (let ((list (make-circular-list n)))
    (flet ((one-element-clist-p (list)
             (eq list (cdr list)))
           (move-forward ()
             (loop repeat (1- d)
                   until (eq list (cdr list))
                   do (setf list (cdr list))))
           (kill-item ()
             (setf (car list) (cadr list)
                   (cdr list) (cddr list))))
      (loop until (one-element-clist-p list) do
            (move-forward)
            (kill-item))
      (first list))))
Example:
CL-USER > (kill 41 3)
30

Crystal[edit]

Translation of: Ruby
n = ARGV.fetch(0, 41).to_i  # n default is 41 or ARGV[0]
k = ARGV.fetch(1,  3).to_i  # k default is 3 or ARGV[1]

prisoners = (0...n).to_a
while prisoners.size > 1; prisoners.rotate!(k-1).shift end
puts "From #{n} prisoners, eliminating each prisoner #{k} leaves prisoner #{prisoners.first}."
Output:
$ crystal josephus.cr
From 41 prisoners, eliminating each prisoner 3 leaves prisoner 30.

$ crystal josephus.cr 123
From 123 prisoners, eliminating each prisoner 3 leaves prisoner 54.

$ crystal josephus.cr 123 47
From 123 prisoners, eliminating each prisoner 47 leaves prisoner 101.

D[edit]

Translation of: Python
import std.stdio, std.algorithm, std.array, std.string, std.range;

T pop(T)(ref T[] items, in size_t i) pure /*nothrow*/ @safe /*@nogc*/ {
    auto aux = items[i];
    items = items.remove(i);
    return aux;
}

string josephus(in int n, in int k) pure /*nothrow*/ @safe {
    auto p = n.iota.array;
    int i;
    immutable(int)[] seq;
    while (!p.empty) {
        i = (i + k - 1) % p.length;
        seq ~= p.pop(i);
    }

    return format("Prisoner killing order:\n%(%(%d %)\n%)." ~
                  "\nSurvivor: %d",
                  seq[0 .. $ - 1].chunks(20), seq[$ - 1]);
}

void main() /*@safe*/ {
    josephus(5, 2).writeln;
    writeln;
    josephus(41, 3).writeln;
}
Output:
Prisoner killing order:
1 3 0 4.
Survivor: 2

Prisoner killing order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27
31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15.
Survivor: 30


Translation of: Javascript
import std.stdio, std.algorithm, std.range;
 
int[][] Josephus(in int n, int k, int s=1) {
    int[] ks, ps = n.iota.array;
    for (int i=--k; ps.length>s; i=(i+k)%ps.length) {
        ks ~= ps[i];
        ps = remove(ps, i);
    }
    writefln("Josephus(%d,%d,%d) -> %(%d %) / %(%d %)%s", n, k, s, ps, ks[0..min($,45)], ks.length<45 ? "" : " ..." );
    return [ps, ks];
}
 
void main() {
    Josephus(5, 2);
    Josephus(41, 3);
    Josephus(23482, 3343, 3);
}}
Output:
Josephus(5,1,1) -> 2 / 1 3 0 4
Josephus(41,2,1) -> 30 / 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Josephus(23482,3342,3) -> 1087 1335 13317 / 3342 6685 10028 13371 16714 20057 23400 3261 6605 9949 13293 16637 19981 23325 3187 6532 9877 13222 16567 19912 23257 3120 6466 9812 13158 16504 19850 23196 3060 6407 9754 13101 16448 19795 23142 3007 6355 9703 13051 16399 19747 23095 2961 6310 9659 ...

EchoLisp[edit]

We use a circular list and apply the 'process'. Successive rests are marked 🔫 (killed) or 😥 (remaining). NB: the (mark) function marks lists and sub-lists, not items in lists. The printed mark appears before the first item in the list.

;; input
(define N 41)
(define K 3)
(define prisoners (apply circular-list (iota N)))
(define last-one prisoners) ; current position

;; kill returns current position = last killed
(define (kill lst skip)
(cond
    ((eq? (mark? lst) '🔫 )(kill (cdr lst) skip)) ;; dead ? goto next
    ((zero? skip) (mark lst '🔫)) ;; all skipped ? kill
    (else (mark lst '😥 )  ;; relieved face
           (kill (cdr lst ) (1- skip))))) ;; skip 1 and goto next
Output:
;; kill N-1
    (for ((i (1- N) )) (set! last-one (kill last-one  (1- K))))
;; look at prisoners
prisoners
 ( 🔄 🔫 0 🔫 1 🔫 2 🔫 3 🔫 4 🔫 5 🔫 6 🔫 7 🔫 8 🔫 9 🔫 10 🔫 11 🔫 12 🔫 13 🔫 14 🔫 15 🔫 16
 🔫 17 🔫 18 🔫 19 🔫 20 🔫 21 🔫 22 🔫 23 🔫 24 🔫 25 🔫 26 🔫 27 🔫 28 🔫 29 😥 30 🔫 31 🔫 32 
 🔫 33 🔫 34 🔫 35 🔫 36 🔫 37 🔫 38 🔫 39 🔫 40 🔫 0 🔫 1   ) 

;; #30 seems happy
;; kill last
(set! last-one (kill last-one (1- K)))
last-one
   ( 🔫 30 🔫 31 🔫 32 …🔃 ) ;; #30 was the last

;; extra : we want more survivors
(define SURVIVORS 3)
(for ((i (- N SURVIVORS) )) (set! last-one (kill last-one  (1- K))))

prisoners
  ( 🔄 🔫 0 🔫 1 🔫 2 🔫 3 🔫 4 🔫 5 🔫 6 🔫 7 🔫 8 🔫 9 🔫 10 🔫 11 🔫 12 🔫 13 🔫 14 😥 15 🔫 16 
   🔫 17 🔫 18 🔫 19 🔫 20 🔫 21 🔫 22 🔫 23 🔫 24 🔫 25 🔫 26 🔫 27 🔫 28 🔫 29 😥 30 🔫 31 🔫 32 
   🔫 33 😥 34 🔫 35 🔫 36 🔫 37 🔫 38 🔫 39 🔫 40 🔫 0 🔫 1  🔫 0  )

Eiffel[edit]

class
	APPLICATION

create
	make

feature

	make
		do
			io.put_string ("Survivor is prisoner: " + execute (12, 4).out)
		end

	execute (n, k: INTEGER): INTEGER
			-- Survivor of 'n' prisoners, when every 'k'th is executed.
		require
			n_positive: n > 0
			k_positive: k > 0
			n_larger: n > k
		local
			killidx: INTEGER
			prisoners: LINKED_LIST [INTEGER]
		do
			create prisoners.make
			across
				0 |..| (n - 1) as c
			loop
				prisoners.extend (c.item)
			end
			io.put_string ("Prisoners are executed in the order:%N")
			killidx := 1
			from
			until
				prisoners.count <= 1
			loop
				killidx := killidx + k - 1
				from
				until
					killidx <= prisoners.count
				loop
					killidx := killidx - prisoners.count
				end
				io.put_string (prisoners.at (killidx).out + "%N")
				prisoners.go_i_th (killidx)
				prisoners.remove
			end
			Result := prisoners.at (1)
		ensure
			Result_in_range: Result >= 0 and Result < n
		end

end
Output:
Prisoners are executed in the order:
3 
7 
11 
4 
9 
2 
10 
6 
5 
8 
1
Survivor is prisoner: 0

Elixir[edit]

defmodule Josephus do
  def find(n,k) do
    find(Enum.to_list(0..n-1),0..k-2,k..n)
  end

  def find([_|[r|_]],_,_..d) when d < 3 do
    IO.inspect r
  end

  def find(arr,a..c,b..d) when length(arr) >= 3 do
    find(Enum.slice(arr,b..d) ++ Enum.slice(arr,a..c),a..c,b..d-1)
  end
end

Josephus.find(41,3)
Output:
30

Emacs Lisp[edit]

(defun jo (n k)
  (if (= 1 n)
      1
    (1+ (% (+ (1- k)
              (jo (1- n) k))
           n))))

(message "%d" (jo 50 2))
(message "%d" (jo 60 3))
Output:
37
41

Erlang[edit]

-module( josephus_problem ).

-export( [general_solution/3, task/0] ).

general_solution( Prisoners, Kill, Survive ) -> general_solution( Prisoners, Kill, Survive, erlang:length(Prisoners), [] ).

task() -> general_solution( lists:seq(0, 40), 3, 1 ).



general_solution( Prisoners, _Kill, Survive, Survive, Kills ) ->
        {Prisoners, lists:reverse(Kills)};
general_solution( Prisoners, Kill, Survive, Prisoners_length, Kills ) ->
        {Skipped, [Killed | Rest]} = kill( Kill, Prisoners, Prisoners_length ),
        general_solution( Rest ++ Skipped, Kill, Survive, Prisoners_length - 1, [Killed | Kills] ).

kill( Kill, Prisoners, Prisoners_length ) when Kill < Prisoners_length ->
    lists:split( Kill - 1, Prisoners );
kill( Kill, Prisoners, Prisoners_length ) ->
    kill_few( Kill rem Prisoners_length, Prisoners ).

kill_few( 0, Prisoners ) ->
    [Last | Rest] = lists:reverse( Prisoners ),
    {lists:reverse( Rest ), [Last]};
kill_few( Kill, Prisoners ) ->
    lists:split( Kill - 1, Prisoners ).
Output:
11> josephus_problem:task().        
{[30],
 [2,5,8,11,14,17,20,23,26,29,32,35,38,0,4,9,13,18,22,27,31,
  36,40,6,12,19,25|...]}

The general solution can handle other items than numbers.

12> josephus_problem:general_solution( [joe, jack, william, averell, ratata], 2, 1 ).
{[william],[jack,averell,joe,ratata]}

ERRE[edit]

PROGRAM JOSEPHUS

!
! for rosettacode.org
!

!$INTEGER

DIM DEAD[100]

PROCEDURE MAIN(N,K,S->ERRORS)
! n - number of prisoners
! k - kill every k'th prisoner
! s - number of survivors
    LOCAL KILLED$,SURVIVED$,FOUND,P,NN,I
    ERRORS=0
    FOR I=0 TO 100 DO
        DEAD[I]=0
    END FOR   ! prepare array
    PRINT("N=";N,"K=";K,"S=";S)        ! show arguments
    IF S>N THEN PRINT("S>N";) ERRORS+=1 END IF
    IF K<=0 THEN PRINT("K<=0";) ERRORS+=1 END IF
    IF ERRORS>0 THEN EXIT PROCEDURE END IF
    NN=N                               ! wrap around boundary
    P=-1                               ! start here
    WHILE N<>S DO                      ! until survivor count is met
      FOUND=0                          ! start looking
      WHILE FOUND<>K DO                ! until we have the k-th prisoner
        P+=1
        IF P=NN THEN P=0 END IF        ! wrap around
        IF DEAD[P]<>1 THEN
            FOUND+=1
        END IF                         ! if prisoner is alive increment found
      END WHILE
      DEAD[P]=1                        ! kill the unlucky one
      KILLED$=KILLED$+STR$(P)          ! build killed list
      N-=1                             ! reduce size of circle
    END WHILE
    FOR I=0 TO NN-1 DO
      IF DEAD[I]<>1 THEN
        SURVIVED$=SURVIVED$+STR$(I)    ! build survivor list
      END IF
    END FOR
    PRINT("Killed:";KILLED$)
    PRINT("Survived:";SURVIVED$)
END PROCEDURE

BEGIN
    ERRORS=0
    MAIN(5,2,1->ERRORS)
    MAIN(41,3,1->ERRORS)
    MAIN(41,3,3->ERRORS)
END PROGRAM

Note: Adapted from AWK version! Output is the same.

Factor[edit]

USING: kernel locals math math.ranges sequences ;
IN: josephus

:: josephus ( k n -- m )
    n [1,b] 0 [ [ k + ] dip mod ] reduce ;
IN: scratchpad 3 41 josephus .
30

Forth[edit]

: josephus  0 1 begin dup 41 <= while  swap 3 + over mod swap  1+ repeat drop ;
josephus . 
30

Fortran[edit]

Naive approach: prisonners are put in a "linked buffer" (implemented as an array giving number of "next living prisonner"). Then we iterate, killing one after each loop, until there is only one left.

program josephus
   implicit none
   integer :: n, i, k, p
   integer, allocatable :: next(:)
   read *, n, k
   allocate(next(0:n - 1))
   do i = 0, n - 2
      next(i) = i + 1
   end do
   next(n - 1) = 0
   p = 0
   do while(next(p) /= p)
      do i = 1, k - 2
         p = next(p)
      end do
      print *, "Kill", next(p)
      next(p) = next(next(p))
      p = next(p)
   end do
   print *, "Alive", p
   deallocate(next)
end program

FreeBASIC[edit]

Function Josephus (n As Integer, k As Integer, m As Integer) As Integer
    Dim As Integer lm = m
    For i As Integer = m + 1  To n
        lm = (lm + k) Mod i
    Next i
    Josephus = lm
End Function

Dim As Integer n = 41 'prisioneros
Dim As Integer k = 3  'orden de ejecución

Print "n ="; n, "k ="; k, "superviviente = "; Josephus(n, k, 0)
Output:
n = 41        k = 3         superviviente =  30

friendly interactive shell[edit]

function execute
    # If the list is empty, don't do anything.
    test (count $argv) -ge 2; or return
    # If the list has only one element, return it
    if test (count $argv) -eq 2
        echo $argv[2]
        return
    end
    # Rotate prisoners
    for i in (seq 2 $argv[1])
        set argv $argv[1 3..-1 2]
    end
    # Mention killed prisoner
    echo $argv[2]
    # Kill rest recursively
    execute $argv[1 3..-1]
end

echo Prisoner (execute 3 (seq 0 40))[-1] survived.
Output:
Prisoner 30 survived.

It's also possible to calculate more than one survivor.

echo Prisoners (execute 3 (seq 0 40))[-3..-1] survived.
Output:
Prisoners 34 15 30 survived.

Prisoners don't have to be numbers.

echo Prisoner (execute 2 Joe Jack William Averell Rantanplan)[-1] survived.
Output:
Prisoner William survived.

Frink[edit]

killingCycle[prisonerCount,killStep = 2] :=
{
   i = 0
   killed = new array
   prisoners = array[0 to prisonerCount - 1]
   while length[prisoners] > 1
   {
      i = (i + killStep - 1) mod length[prisoners]
      killed.push[prisoners.remove[i]] // Remove the killed prisoner from the prisoners array and add it to the killed array.
   }
   killedResult = "Killed:"
   for kill = killed // Loop through the killed array to format it nicely.
   {
      killedResult = killedResult + " " + kill
   }
   aliveResult = "Alive: " + prisoners@0 // Get the only item left in the array
   return """$killedResult
$aliveResult"""
}

println[killingCycle[41,3]] // Enter in total number of prisoners and the number to skip each cycle
Output:
Killed: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Alive: 30

Fōrmulæ[edit]

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

In this page you can see the program(s) related to this task and their results.

Go[edit]

package main

import "fmt"

// basic task function
func finalSurvivor(n, k int) int {
    // argument validation omitted
    circle := make([]int, n)
    for i := range circle {
        circle[i] = i
    }
    k--
    exPos := 0
    for len(circle) > 1 {
        exPos = (exPos + k) % len(circle)
        circle = append(circle[:exPos], circle[exPos+1:]...)
    }
    return circle[0]
}

// extra
func position(n, k, pos int) int {
    // argument validation omitted
    circle := make([]int, n)
    for i := range circle {
        circle[i] = i
    }
    k--
    exPos := 0
    for len(circle) > 1 {
        exPos = (exPos + k) % len(circle)
        if pos == 0 {
            return circle[exPos]
        }
        pos--
        circle = append(circle[:exPos], circle[exPos+1:]...)
    }
    return circle[0]
}

func main() {
    // show basic task function on given test case
    fmt.Println(finalSurvivor(41, 3))
    // show extra function on all positions of given test case
    fmt.Println("Position  Prisoner")
    for i := 0; i < 41; i++ {
        fmt.Printf("%5d%10d\n", i, position(41, 3, i))
    }
}
Output:
30
Position  Prisoner
    0         2
    1         5
    2         8
    3        11
    4        14
    5        17
    6        20
    7        23
    8        26
    9        29
   10        32
   11        35
   12        38
   13         0
   14         4
   15         9
   16        13
   17        18
   18        22
   19        27
   20        31
   21        36
   22        40
   23         6
   24        12
   25        19
   26        25
   27        33
   28        39
   29         7
   30        16
   31        28
   32        37
   33        10
   34        24
   35         1
   36        21
   37         3
   38        34
   39        15
   40        30

Groovy[edit]

int[] Josephus (int size, int kill, int survivors) {
    // init user pool
    def users = new int[size];
    
    // give initial values such that [0] = 1 (first person) [1] = 2 (second person) etc
    users.eachWithIndex() {obj, i -> users[i] = i + 1};
    
    // keep track of which person we are on (ranging from 1 to kill)
    def person = 1;
    
    // keep going until we have the desired number of survivors
    while (users.size() > survivors)
    {
        // for each person, if they are the kill'th person, set them to -1 to show eliminated
        users.eachWithIndex() {obj, i ->
            if (person++ % kill == 0) {
                users[i] = -1;
            }
            
            // if person overflowed kill then reset back to 1
            if (person > kill) {person = 1;}
        }
        
        // clear out all eliminated persons
        users = users.findAll{w -> w >= 0};
    }
    
    // resulting set is the safe positions
    return users;
}

// Run some test cases

println "Final survivor for n = 10201 and k = 17: " + Josephus(10201,17,1)[0];

println "4 safe spots for n = 10201 and k = 17: " + Josephus(10201,17,4);
Output:
Final survivor for n = 10201 and k = 17: 7450
4 safe spots for n = 10201 and k = 17: [3413, 7244, 7450, 7605]

Haskell[edit]

Shows only the surviving prisoners. Change "print $ snd" to just "print" to show the killed prisoners, too. The arguments to the "main" function are: n = number of prisoners, k = kill every kth prisoner, m = show at most m survivors

import Data.List ((\\))
import System.Environment (getArgs)

prisoners :: Int -> [Int]
prisoners n = [0 .. n - 1]

counter :: Int -> [Int]
counter k = cycle [k, k-1 .. 1]

killList :: [Int] -> [Int] -> ([Int], [Int], [Int])
killList xs cs = (killed, survivors, newCs)
    where
        (killed, newCs) = kill xs cs []
        survivors = xs \\ killed
        kill [] cs rs = (rs, cs)
        kill (x:xs) (c:cs) rs
            | c == 1 =
                let ts = rs ++ [x]
                in  kill xs cs ts
            | otherwise =
                kill xs cs rs

killRecursive :: [Int] -> [Int] -> Int -> ([Int], [Int])
killRecursive xs cs m = killR ([], xs, cs)
    where
        killR (killed, remaining, counter)
            | length remaining <= m = (killed, remaining)
            | otherwise =
                let (newKilled, newRemaining, newCounter) =
                        killList remaining counter
                    allKilled = killed ++ newKilled
                in  killR (allKilled, newRemaining, newCounter)

main :: IO ()
main = do
    args <- getArgs
    case args of
        [n, k, m] -> print $ snd $ killRecursive (prisoners (read n))
                        (counter (read k)) (read m)
        _         -> print $ snd $ killRecursive (prisoners 41) (counter 3) 1

Using modulo and list split, indices are 1-based. This is much faster than cycled list for larger numbers:

jseq :: Int -> Int -> [Int]
jseq n k = f n [1 .. n]
  where
    f 0 _ = []
    f m s = x : f (m - 1) (right ++ left)
      where
        (left, x:right) = splitAt (mod (k - 1) m) s

-- the final survivor is ((k + ...((k + ((k + 0)`mod` 1)) `mod` 2) ... ) `mod` n)
jos :: Int -> Int -> Int
jos n k = 1 + foldl (mod . (k +)) 0 [2 .. n]

main :: IO ()
main = do
  print $ jseq 41 3
  print $ jos 10000 100

Icon and Unicon[edit]

The following works in both languages.

procedure main(A)
   m := integer(A[1]) | 41
   c := integer(A[2]) | 3
   write("With ",m," men, counting to ",c," last position is: ", j(m,c))
end

procedure j(m,c)
   return if m==1 then 0 else (j(m-1,c)+c)%m
end
Output:
->josephus
With 41 men, counting to 3 last position is: 30
->

Extra 'credit' version:

This is done awkwardly, but I've had this laying around since the late 1980's...

procedure main(args)
   n := total := integer(args[1]) | 41		# Number of people
   k := count := integer(args[2]) | 3		# Count
   s := integer(args[3])-1 | 0                  # Number to save
   write("With ",n," people, counting by ",k,", the ",s+1," safe places are:")
   every write("\t",j(n,k,(n-s) to n))
end

procedure j(n,k,s)
   a := k*(n-s) + 1
   q := k/(k-1.0)
   nk := n*k
   olda := a
   while a <= nk do {
      olda := a
      a := ceil(a,q)
      }
   t := nk - olda
   return t
end

procedure ceil(a,q)
  n := a*q
  if n = integer(n) then return integer(n)
  n ?:= integer(tab(upto('.'))) + 1
  return n
end

Sample run:

->josephus2 41 3 4
With 41 people, counting by 3, the 4 safe places are:
	3
        34
        15
        30
->

J[edit]

Using the executioner's algorithm.

Tacit version[edit]

   3 ([ (1 }. <:@[ |. ])^:(1 < #@])^:_ i.@]) 41
30

Structured derivation of the fixed tacit code

   DropNext=. 1 }. <:@[ |. ]
   MoreThanOne=. 1 < #@]
   WhileMoreThanOne=. (^:MoreThanOne f.) (^:_)
   prisoners=. i.@]
   
   [ DropNext WhileMoreThanOne prisoners f.
[ (1 }. <:@[ |. ])^:(1 < #@])^:_ i.@]

Explicit version[edit]

Josephus =: dyad define NB. explicit form, assume executioner starts at position 0
 NB. use:  SKIP josephus NUMBER_OF_PRISONERS
 N =: y
 K =: N | x
 EXECUTIONER =: 0
 PRISONERS =: i. N
 kill =: ] #~ (~: ([: i. #))
 while. 1 (< #) PRISONERS do.
  EXECUTIONER =: (# PRISONERS) | <: K + EXECUTIONER
  PRISONERS =: EXECUTIONER kill PRISONERS
 end.
)
    
   3 Josephus 41
30


Explicit version 2[edit]

   NB. this is a direct translation of the algo from C code above.
   Josephus2 =: 4 : '(| x&+)/i. - 1+y' 

   3 Josephus2 41
30

Java[edit]

Works with: Java version 1.5+
import java.util.ArrayList;

public class Josephus {
    public static int execute(int n, int k){
        int killIdx = 0;
        ArrayList<Integer> prisoners = new ArrayList<Integer>(n);
        for(int i = 0;i < n;i++){
            prisoners.add(i);
        }
        System.out.println("Prisoners executed in order:");
        while(prisoners.size() > 1){
            killIdx = (killIdx + k - 1) % prisoners.size();
            System.out.print(prisoners.get(killIdx) + " ");
            prisoners.remove(killIdx);
        }
        System.out.println();
        return prisoners.get(0);
    }
    
    public static ArrayList<Integer> executeAllButM(int n, int k, int m){
        int killIdx = 0;
        ArrayList<Integer> prisoners = new ArrayList<Integer>(n);
        for(int i = 0;i < n;i++){
            prisoners.add(i);
        }
        System.out.println("Prisoners executed in order:");
        while(prisoners.size() > m){
            killIdx = (killIdx + k - 1) % prisoners.size();
            System.out.print(prisoners.get(killIdx) + " ");
            prisoners.remove(killIdx);
        }
        System.out.println();
        return prisoners;
    }
    
    public static void main(String[] args){
        System.out.println("Survivor: " + execute(41, 3));
        System.out.println("Survivors: " + executeAllButM(41, 3, 3));
    }
}
Output:
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 
Survivor: 30
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 
Survivors: [15, 30, 34]
Translation of: Javascript
import java.util.ArrayList;
import java.util.List;

public class Josephus {

	public static void main(String[] args) {
		execute(5, 1);
		execute(41, 2);
		execute(23482, 3342, 3);
	}

	public static int[][] execute(int n, int k) {
		return execute(n, k, 1);
	}

	public static int[][] execute(int n, int k, int s) {
		List<Integer> ps = new ArrayList<Integer>(n);
		for (int i=0; i<n; i+=1) ps.add(i);
		List<Integer> ks = new ArrayList<Integer>(n-s);
		for (int i=k; ps.size()>s; i=(i+k)%ps.size()) ks.add(ps.remove(i));
		System.out.printf("Josephus(%d,%d,%d) -> %s / %s\n", n, k, s, toString(ps), toString(ks));
		return new int[][] {
			ps.stream().mapToInt(Integer::intValue).toArray(),
			ks.stream().mapToInt(Integer::intValue).toArray()
		};
	}
	
	private static String toString(List <Integer> ls) {
		String dot = "";
		if (ls.size() >= 45) {
			dot = ", ...";
			ls = ls.subList(0, 45);
		}
		String s = ls.toString();
		return s.substring(1, s.length()-1) + dot;
	}
}
Output:
Josephus(5,1,1) -> 2 / 1, 3, 0, 4
Josephus(41,2,1) -> 30 / 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15
Josephus(23482,3342,3) -> 1087, 1335, 13317 / 3342, 6685, 10028, 13371, 16714, 20057, 23400, 3261, 6605, 9949, 13293, 16637, 19981, 23325, 3187, 6532, 9877, 13222, 16567, 19912, 23257, 3120, 6466, 9812, 13158, 16504, 19850, 23196, 3060, 6407, 9754, 13101, 16448, 19795, 23142, 3007, 6355, 9703, 13051, 16399, 19747, 23095, 2961, 6310, 9659, ...

JavaScript[edit]

Labels are 1-based, executioner's solution:

var Josephus = {
  init: function(n) {
    this.head = {};
    var current = this.head;
    for (var i = 0; i < n-1; i++) {
      current.label = i+1;
      current.next = {prev: current};
      current = current.next;
    }
    current.label = n;
    current.next = this.head;
    this.head.prev = current;
    return this;
  },
  kill: function(spacing) {
    var current = this.head;
    while (current.next !== current) {
      for (var i = 0; i < spacing-1; i++) {
        current = current.next;
      }
      current.prev.next = current.next;
      current.next.prev = current.prev;
      current = current.next;
    }
    return current.label;
  }
}
Output:
> Josephus.init(30).kill(2)
29

With Array methods:

function Josephus(n, k, s) {
	s = s | 1
	for (var ps=[], i=n; i--; ) ps[i]=i
	for (var ks=[], i=--k; ps.length>s; i=(i+k)%ps.length) ks.push(ps.splice(i, 1))
	document.write((arguments.callee+'').split(/\s|\(/)[1], '(', [].slice.call(arguments, 0), ') -> ', ps, ' / ', ks.length<45?ks:ks.slice(0,45)+',...' , '<br>')
	return [ps, ks]
}
Output:
Josephus(5,1) -> 2 / 1,3,0,4
Josephus(41,2) -> 30 / 2,5,8,11,14,17,20,23,26,29,32,35,38,0,4,9,13,18,22,27,31,36,40,6,12,19,25,33,39,7,16,28,37,10,24,1,21,3,34,15
Josephus(23482,3342,3) -> 1087,1335,13317 / 3342,6685,10028,13371,16714,20057,23400,3261,6605,9949,13293,16637,19981,23325,3187,6532,9877,13222,16567,19912,23257,3120,6466,9812,13158,16504,19850,23196,3060,6407,9754,13101,16448,19795,23142,3007,6355,9703,13051,16399,19747,23095,2961,6310,9659,...

jq[edit]

Works with: jq version 1.4

This section illustrates how a simulation can be directly modeled in jq while being fast enough to solve problems such as [n,k,m] = [23482, 3343, 3].

The prisoners are numbered from 0 to (n-1) in keeping with jq's array index origin of 0, but the nature of their labeling is immaterial to the algorithm.

# A control structure, for convenience:
# as soon as "condition" is true, then emit . and stop:
def do_until(condition; next):
  def u: if condition then . else (next|u) end;
  u;

# n is the initial number; every k-th prisoner is removed until m remain.
# Solution by simulation
def josephus(n;k;m):
    reduce range(0;n) as $i ([]; . + [$i])    # Number the prisoners from 0 to (n-1)
    | do_until( length < k or length <= m; .[k:] + .[0:k-1] )
    | do_until( length <= m; (k % length) as $i | .[$i:] + .[0:$i-1] );

Examples:

def task(n;k;m):
   "Survivors for n=\(n), k=\(k), m=\(m): \( josephus(n;k;m) )";

task(41;3;1),
task(23482; 3343; 3)
Output:
$ jq -M -r -n -f josephus.jq
Survivors for n=41, k=3, m=1: [30]
Survivors for n=23482, k=3343, m=3: [13317,1087,1335]

Julia[edit]

Works with: Julia version 0.6

Recursive (with Memoize):

using Memoize
@memoize josephus(n::Integer, k::Integer, m::Integer=1) = n == m ? collect(0:m .- 1) : mod.(josephus(n - 1, k, m) + k, n)

@show josephus(41, 3)
@show josephus(41, 3, 5)
Output:
josephus(41, 3) = [30]
josephus(41, 3, 5) = [3, 15, 21, 30, 34]

Iterative:

function josephus(n::Integer, k::Integer, m::Integer=1)
    p, i, seq = collect(0:n-1), 0, Vector{typeof(n)}(0)
    while length(p) > m
        i = (i + k - 1) % length(p)
        push!(seq, splice!(p, i + 1))
    end
    return seq, p
end

seq, surv = josephus(41, 3)
println("Prisoner killing in order: $seq\nSurvivor: $surv")

seq, surv = josephus(41, 3, 3)
println("Prisoner killing in order: $seq\nSurvivor: $surv")
Output:
Prisoner killing in order: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15]
Survivor: [30]
Prisoner killing in order: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3]
Survivor: [15, 30, 34]

Kotlin[edit]

// version 1.1.3

fun josephus(n: Int, k: Int, m: Int): Pair<List<Int>, List<Int>> {
    require(k > 0 && m > 0 && n > k && n > m)
    val killed = mutableListOf<Int>()
    val survived = MutableList(n) { it }
    var start = k - 1
    outer@ while (true) {
        val end = survived.size - 1
        var i = start
        var deleted = 0
        while (i <= end) {
            killed.add(survived.removeAt(i - deleted))
            if (survived.size == m) break@outer
            deleted++
            i += k
        } 
        start = i - end - 1
    }
    return Pair(survived, killed)
}
 
fun main(args: Array<String>) {
    val triples = listOf(Triple(5, 2, 1), Triple(41, 3, 1), Triple(41, 3, 3))
    for (triple in triples) {
        val(n, k, m) = triple 
        println("Prisoners = $n, Step = $m, Survivors = $m")
        val (survived, killed)  = josephus(n, k, m)
        println("Survived   : $survived")
        println("Kill order : $killed")
        println()
    }
}
Output:
Prisoners = 5, Step = 1, Survivors = 1
Survived   : [2]
Kill order : [1, 3, 0, 4]

Prisoners = 41, Step = 1, Survivors = 1
Survived   : [30]
Kill order : [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15]

Prisoners = 41, Step = 3, Survivors = 3
Survived   : [15, 30, 34]
Kill order : [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3]

Lua[edit]

Lua indexes tables starting at 1. Positions are stored from 0,n-1.

function josephus(n, k, m)
    local positions={}
    for i=1,n do
        table.insert(positions, i-1)
    end
    local i,j=1,1
    local s='Execution order: '
    while #positions>m do
        if j==k then
            s=s .. positions[i] .. ', '
            table.remove(positions, i)
            i=i-1
        end
        i=i+1
        j=j+1
        if i>#positions then i=1 end
        if j>k then j=1 end
    end
    print(s:sub(1,#s-2) .. '.')
    local s='Survivors: '
    for _,v in pairs(positions) do s=s .. v .. ', ' end
    print(s:sub(1,#s-2) .. '.')
end
josephus(41,3, 1)
Output:
Execution order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15.
Survivors: 30.

Mathematica/Wolfram Language[edit]

survivor[n_, k_] := Nest[Most[RotateLeft[#, k]] &, Range[0, n - 1], n - 1]
survivor[41, 3]
Output:
{30}

MATLAB[edit]

function [indAlive] = josephus(numPeople,count)
% Josephus: Given a circle of numPeople individuals, with a count of count,
% find the index (starting at 1) of the survivor [see Josephus Problem]

%% Definitions:
%   0 = dead position
%   1 = alive position
%   index = # of person

%% Setting up
arrPeople = ones(1, numPeople);
currInd = 0;

%% Counting
while (length(arrPeople(arrPeople == 1)) > 1)     % While more than 1 person is alive
    counter = 0;
    while counter ~= count                       % Counting until we hit the count
        currInd = currInd + 1;                  % Move to the next person
        
        if currInd > numPeople                  % If overflow, wraparound
            currInd = currInd - numPeople;
        end
        
        if arrPeople(currInd)                   % If the current person is alive
            counter = counter + 1;                % Add 1 person to the count
            %fprintf("Index: %d \t| Counter: %d\n", currInd, counter)           % Uncomment to display index and counter location
        end

    end
    
    arrPeople(currInd) = 0;                     % Kill the person we reached
    %fprintf("Killed person %d \n", currInd)                                   % Uncomment to display order of killing
    %disp(arrPeople)                                                           % Uncomment to display current status of people
end

indAlive = find(arrPeople);

end

Modula-2[edit]

MODULE Josephus;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

PROCEDURE Josephus(n,k : INTEGER) : INTEGER;
VAR a,m : INTEGER;
BEGIN
    m := 0;
    FOR a:=1 TO n DO
        m := (m + k) MOD a;
    END;
    RETURN m
END Josephus;

VAR
    buf : ARRAY[0..63] OF CHAR;
    n,k,i : INTEGER;
    nl,kl,il : LONGCARD;
BEGIN
    n := 41;
    k := 3;
    FormatString("n = %i, k = %i, final survivor: %i\n", buf, n, k, Josephus(n, k));
    WriteString(buf);

    ReadChar
END Josephus.

Nanoquery[edit]

Translation of: Python
def j(n, k)
        p = list(range(0, n-1))
        i = 0
        seq = {}
        while len(p) > 0
                i = (i+k-1) % len(p)
                seq.append(p[i])
                p.remove(i)
        end
        sur = seq[len(seq) - 1]; seq.remove(len(seq) - 1)
        return format("Prisoner killing order: %s\nSurvivor: %d", seq, sur)
end

println j(5,2)
println
println j(41,3)
Output:
Prisoner killing order: [1, 3, 0, 4]
Survivor: 2

Prisoner killing order: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15]
Survivor: 30

NetRexx[edit]

Translation of: REXX

Hardly any changes at all...

/* NetRexx */
options replace format comments java crossref symbols nobinary

/* 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
**********************************************************************/
dead = 0                               /* nobody's dead yet          */
n = 41                                 /* number of alive prisoners  */
nn = n                                 /* wrap around boundary       */
w = 3                                  /* killing count              */
s = 1                                  /* nuber of survivors         */
p = -1                                 /* start here                 */
killed = ''                            /* output of killings         */
Loop until n = s                       /* until one alive prisoner   */
  found = 0                            /* start looking              */
  Loop 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
  n = n - 1                            /* shoot the one on this pos. */
  killed = killed p                    /* add to output              */
  End                                  /* End of main loop           */
Say 'killed:'killed.subword(1, 20)     /* output killing sequence    */
Say '       'killed.subword(21)        /* output killing sequence    */
Say 'Survivor(s):'                     /* show                       */
Loop i = 0 To 40                       /* look for the surviving p's */
  If dead[i] = 0 Then Say i            /* found one                  */
  End
Output:
killed:2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27
       31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Survivor(s):
30

Nim[edit]

Simulating[edit]

Translation of: Python
import sequtils, strutils, sugar

proc j(n, k: int): string =
  var
    p = toSeq(0 ..< n)
    i = 0
    s = newSeq[int]()

  while p.len > 0:
    i = (i + k - 1) mod p.len
    s.add p[i]
    system.delete(p, i)

  result = "Prisoner killing order: "
  result.add s.map((x: int) => $x).join(", ")
  result.add ".\nSurvivor: "
  result.add($s[s.high])

echo j(5,2)
echo j(41,3)
Output:
Prisoner killing order: 1, 3, 0, 4, 2.
Survivor: 2
Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15, 30.
Survivor: 30

Processing backwards[edit]

Another more efficient way but without the killing order:

func prisonerPos(n, k: Positive): int =
  ## The result is computed backwards. We start from the winner at
  ## position 0 on last round and compute its position on previous rounds.
  var pos = 0
  for i in 2..n:
    pos = (pos + k) mod i
  result = pos

echo "Survivor: ", prisonerPos(5, 2)
echo "Survivor: ", prisonerPos(41, 3)
Output:
Survivor: 2
Survivor: 30

Objeck[edit]

class Josephus {
  function : Execute(n : Int, k : Int) ~ Int {
    killIdx := 0;
    prisoners := Collection.IntVector->New();
    for(i := 0;i < n;i+=1;){
      prisoners->AddBack(i);
    };
    
    "Prisoners executed in order:"->PrintLine();
    while(prisoners->Size() > 1){
      killIdx := (killIdx + k - 1) % prisoners->Size();
      executed := prisoners->Get(killIdx);
      "{$executed} "->Print();
      prisoners->Remove(killIdx);
    };
    '\n'->Print();    
    return prisoners->Get(0);
  }
  
  function : ExecuteAllButM(n : Int, k : Int, m : Int) ~ Collection.IntVector {
    killIdx := 0;
    prisoners := Collection.IntVector->New();
    for(i := 0;i < n;i+=1;){
      prisoners->AddBack(i);
    };
    "Prisoners executed in order:"->PrintLine();
    while(prisoners->Size() > m){
      killIdx := (killIdx + k - 1) % prisoners->Size();
      executed := prisoners->Get(killIdx);
      "{$executed} "->Print();
      prisoners->Remove(killIdx);
    };
    '\n'->Print();    
    return prisoners;
  }
  
  function : Main(args : String[]) ~ Nil {
    result := Execute(41, 3);
    "Survivor: {$result}"->PrintLine();

    results := ExecuteAllButM(41, 3, 3);
    "Survivors: "->Print();
    each(i : results) {
    results->Get(i)->Print();
      if(i + 1 < results->Size()) {
        ' '->Print();
      };
    };
  }
}

Oforth[edit]

Oforth lists are 1-based : prisoners are numbered from 1 to n.

: josephus(n, k)
| prisoners killed i |
   n seq asListBuffer ->prisoners
   ListBuffer newSize(n) ->killed

   0 n 1- loop: i [ 
      k 1- + prisoners size mod dup 1+ prisoners removeAt
      killed add 
      ] drop

   System.Out "Killed : " << killed << "\nSurvivor : " << prisoners << cr
;
Output:
>josephus(41, 3)
Killed : [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16]
Survivor : [31]

Oz[edit]

data-driven concurrent version[edit]

Figure 7.35 from "Concepts, Techniques, and Models of Computer Programming" indexes from 1 instead of 0. It was modified to report indexes from 0 and also report the killed list:

declare
fun {Pipe Xs L H F}
   if L=<H then {Pipe {F Xs L} L+1 H F} else Xs end
end
fun {Josephus N K}
   fun {Victim Xs I}
      case Xs of kill(X S)|Xr then
	 if S==1 then Last=I nil
	 elseif X mod K==0 then
	    Killed:=I-1|@Killed
	    kill(X+1 S-1)|Xr
	 else
	    kill(X+1 S)|{Victim Xr I}
	 end
      [] nil then nil end
   end
   Last Zs Killed={NewCell nil}
in
   Zs={Pipe kill(1 N)|Zs 1 N
       fun {$ Is I} thread {Victim Is I} end end}
   result(survivor: Last-1 killed: {Reverse @Killed})
end
{Show {Josephus 41 3}}
Output:
result(killed:2|5|8|11|14|17|20|23|...|... survivor:30)

PARI/GP[edit]

Josephus(n, k)=if(n<2, n>0, my(t=(Josephus(n-1, k)+k)%n); if(t, t, n))

Perl[edit]

Translation of: Raku
my @prisoner = 0 .. 40;
my $k = 3;
until (@prisoner == 1) {
    push @prisoner, shift @prisoner for 1 .. $k-1;
    shift @prisoner;
}

print "Prisoner @prisoner survived.\n"
Output:
Prisoner 30 survived.

Phix[edit]

I managed to identify eight algorithms in use on this page, so I translated all of them. Kill ordering lists omitted for sanity.
Unclassified: Haskell, Python[4 aka learning iter in python], REXX[version 2] (plus Befunge, J, and Mathematica, which I'm happy to ignore)
Note all indexes and results are 1-based. For skipping/linked_list/sliding_queue, prisoners do not have to be numbers, the same would be true for contractacycle and contractalot with the tiniest of tweaks. For recursive/iterative, prisoners are implicitly numbers, not that it would be difficult to use the result(s) to subscript a list of string names.

skipping[edit]

360 assembly, 6502 Assembly, AWK, EchoLisp, ERRE, MATLAB, NetRexx, PHP, PL/I, REXX[version 1].
Method: all prisoners stay where they are, executioner walks round and round, skipping over ever increasing numbers of dead bodies (slowest of the lot, by quite some margin)

function skipping(sequence prisoners, integer step, survivors=1)
    integer n = length(prisoners), nn = n, p = 0
    while n>survivors do
        integer found = 0
        while found<step do
            p = iff(p=nn?1:p+1)
            found += prisoners[p]!=-1
        end while
        prisoners[p] = -1
        n -= 1
    end while
    return remove_all(-1,prisoners)
end function
--?skipping({"Joe","Jack","William","John","James"},2,1) --> {"William"}

linked list[edit]

AArch64 Assembly, Ada, ARM Assembly, Common Lisp[2, probably], Fortran, JavaScript[1] (albeit dbl-lnk), Python[3].
Method: like skipping, all prisoners stay where they are, but the executioner uses the links to speed things up a bit.

function linked_list(sequence prisoners, integer step, survivors)
    integer n = length(prisoners)
    sequence links = tagset(n,2)&1
    integer p = n, prvp
    while n>survivors do
        for i=1 to step do
            prvp = p
            p = links[p]
        end for
        prisoners[p] = -1
        links[prvp] = links[p]
        n -= 1
    end while
    return remove_all(-1,prisoners)
end function

sliding queue[edit]

Clojure, Crystal, D (both), Eiffel, Elixir, Erlang, friendly interactive shell, Go, jq, Perl, PowerShell, PureBasic (albeit one at a time), Quackery, Raku, REBOL, Ruby, Scala, Sidef[1], Tcl, Vlang. Method: all skipped prisoners rejoin the end of the queue which sidles left, executioner stays put until the queue gets too short.

function sliding_queue(sequence prisoners, integer step, survivors)
    integer n = length(prisoners)
    while n>survivors do
        integer k = remainder(step-1,n)+1                   -- (mostly k==step)
        prisoners = prisoners[k+1..$]&prisoners[1..k-1]     -- rotate, dropping one.
        n -= 1
    end while
    return prisoners
end function

contractacycle[edit]

AppleScript[2], Groovy
Method: executioner walks along killing every k'th prisoner; while he walks back the queue contracts to remove gaps. (once the queue gets too small it obviously reverts to one at a time, a bit more like contractalot below)

function contractacycle(integer n, integer k, s)
    sequence living = tagset(n)
    integer startPosition = k, i, lasti
    while n!=s do -- Keep going round the circle until only s prisoners remain.
        integer circleSize = n
        if (n < k) then
            i = mod(startPosition-1,circleSize) + 1
            living = living[1..i-1]&living[i+1..$]
            n -= 1
            lasti = i
        else
            for i=startPosition to circleSize by k do
                living[i] = -1
                n -= 1
                if (n = s) then exit end if -- Not Groovy, see note
                lasti = i
            end for
            living = remove_all(-1,living)
        end if
        startPosition = lasti + k - circleSize
    end while
    return living
end function

Groovy does not have a n=s test, it probably is entirely unnecessary. The Groovy code is also somewhat neater, always using a loop and remove_all() - while not probihitively expensive, it may check lots of things for -1 that the slicing won't.

contractalot[edit]

AutoHotkey, C#, C++, Frink, Formulae, Java (both), JavaScript[2], Julia[2], Kotlin, Lua, NanoQuery, Nim, Objeck, Oforth, Processing, Python[1], R[2], Rust, Seed7, Swift, VBScript, Vedit, VisualBasic.NET, XPL0, zkl.
Method: executioner walks round and round, queue contracts after every kill.

function contractalot(integer n, integer k, s)
    sequence list = tagset(n)
    integer i = 1
    while n>s do
        i += k - 1
        if (i > n) then i := mod(i-1, n)+1 end if
        list [i..i] = {}
        n -= 1
    end while
    return list
end function

recursive[edit]

Emacs Lisp, Icon, Julia[1], PARI/GP, PicoLisp (less the optms.n), Sidef[2]
Method: recursive mod maths madness - only handles the lone survivor case.

function recursive(integer n, k) 
    return iff(n=1?1:1+mod(k-1+(recursive(n-1, k)),n))
end function

iterative[edit]

ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC, Batch File, C (but not ULL), Common Lisp[1], Factor, Forth, FreeBASIC, Modula-2, Python[2], R, Racket, Ring, SequenceL, ZX Spectrum Basic
Method: iterative mod maths madness - but hey, it will be extremely fast. Unlike recursive, it can also deliver >1 survivor, one at a time.

function iterative(integer n, k, m=0)
-- Return m-th on the reversed kill list; m=0 is final survivor.
    for a = m+1 to n do
        m = mod(m+k, a) 
    end for
    return m + 1     -- (make result 1-based)
end function

iterative2[edit]

Icon[2]
Method: more iterative maths madness

function iterative2(integer n,k,s)
    integer a = k*(n-s) + 1,
         olda = a
    atom q = k/(k-1),
        nk = n*k
    while a <= nk do
        olda = a
        a = ceil(a*q)
    end while
    return nk - olda + 1 -- (make result 1-based)
end function

test driver[edit]

--demo/rosetta/Josephus.exw
constant show_all = true,
         show_slow = false,
         show_skipping = false,
         show_linkedlist = false,
         show_sliding_queue = false,
         show_contractacycle = false,
         show_contractalot = false,
         show_recursive = false,
         show_iterative = false,
         show_iterative2 = true

constant TAGSET = #01,
         ITER   = #02,
         ITER2  = #04,
         SLOW   = #08,
         ONES   = #10

constant tests = {{41,3,1,false},
                  {41,3,3,false},
                  {5,2,1,false},
                  {5,4,1,false},
                  {50,2,1,false},
                  {60,3,1,false},
                  {23482,3343,3,true},
                  {23482,3343,1,true},
                  {41,3,6,false}}

procedure test(string name, integer flags)
    atom t0 = time()
    integer rid = routine_id(name)
    for i=1 to length(tests) do
        integer {prisoners, step, survivors, slow} = tests[i]
        if (not and_bits(flags,ONES) or survivors=1)
        and (not slow or show_slow or not and_bits(flags,SLOW)) then
            sequence res
            if and_bits(flags,ONES) then
                -- (recursive does not take a 3rd param)
                res = {rid(prisoners,step)}
            elsif and_bits(flags,TAGSET) then
                res = rid(tagset(prisoners),step,survivors)
            elsif and_bits(flags,ITER) then
                res = {}
                for s=0 to survivors-1 do
                    res &= rid(prisoners,step,s)
                end for
            elsif and_bits(flags,ITER2) then
                res = {}
                for s=prisoners-survivors+1 to prisoners do
                    res &= rid(prisoners,step,s)
                end for
            else
                res = rid(prisoners,step,survivors)
            end if
            printf(1,"%s(%d,%d,%d) = %v\n",{name,prisoners,step,survivors,res})
        end if
    end for
    ?elapsed(time()-t0)
end procedure
if show_all or show_skipping        then test("skipping",TAGSET+SLOW)       end if
if show_all or show_linkedlist      then test("linked_list",TAGSET+SLOW)    end if
if show_all or show_sliding_queue   then test("sliding_queue",TAGSET+SLOW)  end if
if show_all or show_contractacycle  then test("contractacycle",SLOW)        end if
if show_all or show_contractalot    then test("contractalot",NULL)          end if
if show_all or show_recursive       then test("recursive",ONES)             end if
if show_all or show_iterative       then test("iterative",ITER)             end if
if show_all or show_iterative2      then test("iterative2",ITER2)           end if
Output:

As shown for sliding_queue, some of the result sets are in a slightly different order, sometimes, otherwise matching output replaced by "...".

skipping(41,3,1) = {31}
skipping(41,3,3) = {16,31,35}
skipping(5,2,1) = {3}
skipping(5,4,1) = {1}
skipping(50,2,1) = {37}
skipping(60,3,1) = {41}
skipping(23482,3343,3) = {1088,1336,13318}
skipping(23482,3343,1) = {1336}
skipping(41,3,6) = {2,4,16,22,31,35}
"17s"
linked_list(41,3,1) = {31}...
"0.6s"
sliding_queue(41,3,1) = {31}...
sliding_queue(23482,3343,3) = {13318,1088,1336}
sliding_queue(41,3,6) = {31,35,2,4,16,22}
"1.0s"
contractacycle(41,3,1) = {31}...
"1.5s"
contractalot(41,3,1) = {31}...
"0.9s"
recursive(41,3,1) = {31}...
"0.0s"
iterative(41,3,1) = {31}...
"0.0s"
iterative2(41,3,1) = {31}...
"0.0s"

PHP[edit]

<?php //Josephus.php
function Jotapata($n=41,$k=3,$m=1){$m--;
	$prisoners=array_fill(0,$n,false);//make a circle of n prisoners, store false ie: dead=false
	$deadpool=1;//count to next execution
	$order=0;//death order and *dead* flag, ie. deadpool
	while((array_sum(array_count_values($prisoners))<$n)){//while sum of count of unique values dead times < n (they start as all false)
		foreach($prisoners as $thisPrisoner=>$dead){
			if(!$dead){//so yeah...if not dead...
				if($deadpool==$k){//if their time is up in the deadpool...
					$order++;
					//set the deadpool value or enumerate as survivor
					$prisoners[$thisPrisoner]=((($n-$m)>($order)?$order:(($n)==$order?'Call me *Titus Flavius* Josephus':'Joe\'s friend '.(($order)-($n-$m-1)))));
					$deadpool=1;//reset count to next execution
				}else{$duckpool++;}
			}
		}
	}
	return $prisoners;
}
echo '<pre>'.print_r(Jotapata(41,3,5),true).'<pre>';

PicoLisp[edit]

The counting starts from one instead of zero. The last remaining person is returned.

#general solution
(de jo (N K)
   (if (=1 N)
      1
      (inc
         (%
            (+ (dec K) (jo (dec N) K))
            N ) ) ) )

#special case when K is 2; much faster than general version.
(de jo2(N)
   (let P 1
      (while (<= P N)
         (setq P (* 2 P))
         (+ (- (* 2 N) P) 1) ) ) )

# find the survivor using an optimal solution
(de survivor (N K)
   (if (=0 (% N 2))
      (jo2 N)
      (jo N K) ) )
(print (survivor 5 2))
(print (survivor 41 3))
Output:
3
31

PL/I[edit]

*process or(!) source attributes xref;
 joseph: Proc Options(main);
 /* 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
 * 03.05.2013 Walter Pachl Translated From REXX Version 1
 **********************************************************************/
 Dcl dead(0:100) Bit(1);
 Dcl (n,nn,w,s,p,found) Bin Fixed(15);
 Dcl pp Pic'99';
 Dcl killed Char(300) Var Init('killed: '); /* output of killings     */
 Dcl survived Char(300) Var Init('Survivor(s): ');
 dead='';                               /* nobody's dead yet          */
 n=41;                                  /* number of alive prisoners  */
 nn=n;                                  /* wrap around boundary       */
 w=3;                                   /* killing count              */
 s=1;                                   /* number of survivors         */
 p=-1;                                  /* start here                 */
 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) Then                   /* a prisoner who is alive    */
       found=found+1;                   /* increment found count      */
     End;
   dead(p)='1'b;                        /* shoot the one on this pos. */
   n=n-1;
   pp=p;
   killed=killed!!' '!!pp;              /* add to output              */
   End;                                 /* End of main loop           */
 Call o(killed);
 Do i=0 To nn-1;                        /* look for the surviving p's */
   If ^dead(i) Then Do;                 /* found one                  */
     pp=i;
     survived=survived!!' '!!pp;
     End;
   End;
 Call o(survived);

 o: Proc(s);
 /*********************************************************************
 * Formatted Output of given string:
 * xxxxxxxxxx xxx xx xx xxx ---
 *         xx xxx xxx
 *         xxxxx xxx
 *********************************************************************/
 Dcl s Char(*) Var;
 Dcl p Bin Fixed(15);
 Dcl ll Bin Fixed(15) Init(72);
 Do While(length(s)>ll);
   Do p=ll+1 To 10 By -1;
     If substr(s,p,1)=' ' Then
       Leave;
     End;
   Put Edit(left(s,p))(Skip,a);
   s=repeat(' ',8)!!substr(s,p+1);
   End;
 Put Edit(s)(Skip,a);
 End;

 End;
Output:
killed:  02 05 08 11 14 17 20 23 26 29 32 35 38 00 04 09 13 18 22 27 31
         36 40 06 12 19 25 33 39 07 16 28 37 10 24 01 21 03 34 15
Survivor(s):  30 

PowerShell[edit]

Works with: PowerShell version 2

Adapted from the iterative algorithm in Sidef.

Rotating the circle K prisoners is equivalent to the executioner walking around the circle K prisoners. We rotate the circle to bring the next selectee to the "front" of the circle, then "select" him by moving past him to the remaining circle. After repeating through the entire prisoner population, we are left with the prisoners sorted into the order in which they are selected.

The lonely comma in the line where we create the $Prisoners arraylist is to prevent PowerShell from being too helpful. Normally when we present the PowerShell parser with an array within an array, it treats it as a cast, and we end up with the single array of elements. In those cases where we need an array to be treated as a single element of a parent array, we can use the unary comma to force PowerShell to treat it as an element.

function Get-JosephusPrisoners ( [int]$N, [int]$K )
    {
    #  Just for convenience
    $End = $N - 1
 
    #  Create circle of prisoners
    $Prisoners = New-Object System.Collections.ArrayList ( , (0..$End) )
 
    #  For each starting point of the reducing circle...
    ForEach ( $Start in 0..($End - 1) )
        {
        #  We subtract one from K for the one we advanced by incrementing $Start
        #  Then take K modulus the length of the remaining circle
        $RoundK = ( $K - 1 ) % ( $End - $Start + 1 )
       
        #  Rotate the remaining prisoners K places around the remaining circle
        $Prisoners.SetRange( $Start, $Prisoners[ $Start..$End ][ ( $RoundK + $Start - $End - 1 )..( $RoundK - 1 ) ] )
        }
    return $Prisoners
    }
#  Get the prisoner order for a circle of 41 prisoners, selecting every third
$Prisoners = Get-JosephusPrisoners -N 41 -K 3
 
#  Display the prisoner order
$Prisoners -join " "
 
#  Display the last remaining prisoner
"Last prisoner remmaining: " + $Prisoners[-1]
 
#  Display the last three remaining prisoners
$S = 3
"Last $S remaining: " + $Prisoners[-$S..-1]
Output:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30
Last prisoner remmaining: 30
Last 3 remaining: 34 15 30

Processing[edit]

Translation of Java example.

void setup() {
  println("Survivor: " + execute(41, 3));
  println("Survivors: " + executeAllButM(41, 3, 3));
}

int execute(int n, int k) {
  int killIdx = 0;
  IntList prisoners = new IntList(n);
  for (int i = 0; i < n; i++) {
    prisoners.append(i);
  }
  println("Prisoners executed in order:");
  while (prisoners.size() > 1) {
    killIdx = (killIdx + k - 1) % prisoners.size();
    print(prisoners.get(killIdx) + " ");
    prisoners.remove(killIdx);
  }
  println();
  return prisoners.get(0);
}

IntList executeAllButM(int n, int k, int m) {
  int killIdx = 0;
  IntList prisoners = new IntList(n);
  for (int i = 0; i < n; i++) {
    prisoners.append(i);
  }
  println("Prisoners executed in order:");
  while (prisoners.size() > m) {
    killIdx = (killIdx + k - 1) % prisoners.size();
    print(prisoners.get(killIdx) + " ");
    prisoners.remove(killIdx);
  }
  println();
  return prisoners;
}

PureBasic[edit]

NewList prisoners.i()

Procedure f2l(List p.i())
  FirstElement(p())    : tmp.i=p()
  DeleteElement(p(),1) : LastElement(p())
  AddElement(p())      : p()=tmp 
EndProcedure

Procedure l2f(List p.i())
  LastElement(p())   : tmp.i=p()
  DeleteElement(p()) : FirstElement(p())
  InsertElement(p()) : p()=tmp  
EndProcedure

OpenConsole()
Repeat
  Print(#LF$+#LF$)
  Print("Josephus problem - input prisoners : ") : n=Val(Input())
  If n=0 : Break : EndIf  
  Print("                 - input steps     : ") : k=Val(Input())
  Print("                 - input survivors : ") : s=Val(Input()) : If s<1 : s=1 : EndIf
  ClearList(prisoners()) : For i=0 To n-1 : AddElement(prisoners()) : prisoners()=i : Next
  If n<100 : Print("Executed : ") : EndIf
  While ListSize(prisoners())>s And n>0 And k>0 And k<n    
    For j=1 To k : f2l(prisoners()) : Next    
    l2f(prisoners()) : FirstElement(prisoners()) : If n<100 : Print(Str(prisoners())+Space(2)) : EndIf 
    DeleteElement(prisoners())    
  Wend
  Print(#LF$+"Surviving: ")
  ForEach prisoners()
    Print(Str(prisoners())+Space(2))
  Next      
ForEver
End
Output:
Josephus problem - input prisoners : 5
                 - input steps     : 2
                 - input survivors : 1
Executed : 1  3  0  4
Surviving: 2

Josephus problem - input prisoners : 41
                 - input steps     : 3
                 - input survivors : 1
Executed : 2  5  8  11  14  17  20  23  26  29  32  35  38  0  4  9  13  18  22  27  31  36  40  6  12  19  25  33  39  7  16  28  37  10  24  1  21  3  34  15
Surviving: 30

Josephus problem - input prisoners : 41
                 - input steps     : 3
                 - input survivors : 3
Executed : 2  5  8  11  14  17  20  23  26  29  32  35  38  0  4  9  13  18  22  27  31  36  40  6  12  19  25  33  39  7  16  28  37  10  24  1  21  3
Surviving: 15  30  34

Josephus problem - input prisoners : 71
                 - input steps     : 47
                 - input survivors : 11
Executed : 46  22  70  48  26  5  56  36  17  0  54  38  23  9  66  55  43  33  25  16  11  6  2  69  68  1  4  10  15  24  32  42  53  65  20  40  60  19  47  8  44  13  52  31  12  62  57  50  51  61  7  30  59  34  18  3  21  37  67  63
Surviving: 64  14  27  28  29  35  39  41  45  49  58

Josephus problem - input prisoners :

Python[edit]

>>> def j(n, k):
	p, i, seq = list(range(n)), 0, []
	while p:
		i = (i+k-1) % len(p)
		seq.append(p.pop(i))
	return 'Prisoner killing order: %s.\nSurvivor: %i' % (', '.join(str(i) for i in seq[:-1]), seq[-1])

>>> print(j(5, 2))
Prisoner killing order: 1, 3, 0, 4.
Survivor: 2
>>> print(j(41, 3))
Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15.
Survivor: 30
>>>

Faster way[edit]

Does not show the killing order.

>>>def josephus(n, k):
        r = 0
        for i in xrange(1, n+1):
            r = (r+k)%i
        return 'Survivor: %d' %r

>>> print(josephus(5, 2))
Survivor: 2
>>> print(josephus(41, 3))
Survivor: 30
>>>

Alternate solution with a circular linked list[edit]

The function returns the killing order. The last in the list stays alive. Notice that the result is a permutation of [0, 1, ... n - 1]. In the program, a[p] is the index of the next living prisoner after 'p'. The program stops when p = a[p], that is, when there remains only one living prisoner.

def josephus(n, k):
    a = list(range(1, n + 1))
    a[n - 1] = 0
    p = 0
    v = []
    while a[p] != p:
        for i in range(k - 2):
            p = a[p]
        v.append(a[p])
        a[p] = a[a[p]]
        p = a[p]
    v.append(p)
    return v

josephus(10, 2)
[1, 3, 5, 7, 9, 2, 6, 0, 8, 4]

josephus(41, 3)[-1]
30

learning iter in python[edit]

from itertools import compress, cycle
def josephus(prisoner, kill, surviver):
    p = range(prisoner)
    k = [0] * kill
    k[kill-1] = 1
    s = [1] * kill
    s[kill -1] = 0
    queue = p
    
    queue = compress(queue, cycle(s))
    try:
        while True:
            p.append(queue.next())        
    except StopIteration:
        pass 

    kil=[]
    killed = compress(p, cycle(k))
    try:
        while True:
            kil.append(killed.next())
    except StopIteration:
        pass 
        
    print 'The surviver is: ', kil[-surviver:]
    print 'The kill sequence is ', kil[:prisoner-surviver]

josephus(41,3,2)
The surviver is:  [15, 30]
The kill sequence is  [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34]
josephus(5,2,1)
The surviver is:  [2]
The kill sequence is  [1, 3, 0, 4]

Quackery[edit]

Not the fastest method, but illustrates use of ancillary stacks, and using nests as queues.

[ stack ]                      is survivors           (     --> s   )

[ stack ]                      is prisoners           (     --> s   )

[ stack ]                      is executioner-actions (     --> s   )

[ [] swap times [ i^ join ]
  prisoners put ]              is make-prisoners      (   n -->     )

[ prisoners take
  behead join 
  prisoners put ]              is walk                (     -->     )

[ prisoners take
  behead drop
  prisoners put ]              is kill                (     -->     )

[ [] swap 1 - times 
     [ ' walk nested join ]
  ' kill nested join
  executioner-actions put ]    is make-executioner    (   n -->     )

[ executioner-actions take
  behead dup do nested join
  executioner-actions put ]    is execute-kth         (     -->     )

[ survivors put
  make-executioner
  make-prisoners
  [ execute-kth
    prisoners share
    size 
    survivors share = until ]
  survivors release
  executioner-actions release
  prisoners take ]             is josephus             ( n n n --> n )

Testing in Quackery shell:

/O> 41 3 1 josephus
... 41 3 3 josephus
... 

Stack: [ 30 ] [ 15 30 34 ]

R[edit]

Growing circle solution[edit]

jose <-function(s, r,n){
y <- 0:(r-1)
 for (i in (r+1):n)
  y <- (y + s) %% i 
 return(y)
}
> jose(3,1,41) # r is the number of remained prisoner.
[1] 30

Iterative solution[edit]

I hope to be proven wrong, but R seems to be the wrong tool for this problem:

  • It is 1-indexed, meaning that we will have a tough time using most solutions that exploit modular arithmetic.
  • It lacks any concept of a linked list, meaning that we can't take a circular list approach.
  • The idiomatic way to roll an array in R (e.g. as the Ruby solution has) is to exploit the head and tail functions, but those break if we are rolling by more than the length of the array (see https://stackoverflow.com/q/18791212 for a few tricks for this).

Regardless, it is still solvable. The following adapts a great deal of the Lua solution. The arguments n, k, and m are as in the task description.

josephusProblem <- function(n, k, m)
{
  prisoners <- 0:(n - 1)
  exPos <- countToK <- 1
  dead <- integer(0)
  while(length(prisoners) > m)
  {
    if(countToK == k)
    {
      dead <- c(dead, prisoners[exPos])
      prisoners <- prisoners[-exPos]
      exPos <- exPos - 1
    }
    exPos <- exPos + 1
    countToK <- countToK + 1
  if(exPos > length(prisoners)) exPos <- 1
  if(countToK > k) countToK <- 1
  }
  print(paste0("Execution order: ", paste0(dead, collapse = ", "), "."))
  paste0("Survivors: ", paste0(prisoners, collapse = ", "), ".")
}
Output:
> josephusProblem(5, 2, 1)
[1] "Execution order: 1, 3, 0, 4."
[1] "Survivors: 2."
> josephusProblem(41, 3, 1)
[1] "Execution order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15."
[1] "Survivors: 30."
> josephusProblem(41, 3, 3)
[1] "Execution order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3."
[1] "Survivors: 15, 30, 34."

Racket[edit]

#lang racket
(define (josephus n k (m 0))
  (for/fold ((m (add1 m)))
    ((a (in-range (add1 m) (add1 n))))
    (remainder (+ m k) a)))

(josephus 41 3) ; ->30

Raku[edit]

(formerly Perl 6)

Works with: rakudo version 2015-11-12

Straightforward implementation of the executioner's algorithm:

sub Execute(@prisoner, $k) {
    until @prisoner == 1 {
	@prisoner.=rotate($k - 1);
	@prisoner.shift;
    }
}
 
my @prisoner = ^41;
Execute @prisoner, 3;
say "Prisoner {@prisoner} survived.";

# We don't have to use numbers.  Any list will do:

my @dalton = <Joe Jack William Averell Rantanplan>;
Execute @dalton, 2;
say "{@dalton} survived.";
Output:
Prisoner 30 survived.
William survived.

REBOL[edit]

Works in Rebol 2 or 3

Rebol []

execute: func [death-list [block!] kill [integer!]] [
    assert [not empty? death-list]
    until [
        loop kill - 1 [append death-list take death-list]
        (1 == length? remove death-list)
    ]
]

prisoner: [] for n 0 40 1 [append prisoner n]
execute prisoner 3
print ["Prisoner" prisoner "survived"]
Output:
Prisoner 30 survived

And any kind of list will do:

for-the-chop: [Joe Jack William Averell Rantanplan]
execute for-the-chop 2
print [for-the-chop "survived"]
Output:
William survived

REXX[edit]

version 1[edit]

/* 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                       */
Output:
killed: 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Survivor(s): 30

version 2[edit]

This REXX version allows the user to specify:

  •   the number of prisoners
  •   the count-off   [every Kth prisoner]
  •   the start count   [zero or one]
  •   the number of survivors
  •   the solving of the extra credit task requirement of multiple survivors

The output echoes the choices specified and was made "English" readable.

This solution is an   executor's   solution.

/*REXX program solves  Josephus problem:   N  men standing in a circle,  every Kth kilt.*/
parse arg N K Z R .                              /*obtain optional arguments from the CL*/
if N=='' | N==","   then  N= 41                  /*    men  not specified?  Use default.*/
if K=='' | K==","   then  K=  3                  /*   kilt   "      "        "     "    */
if Z=='' | Z==","   then  Z=  0                  /*  start   "      "        "     "    */
if R=='' | R==","   then  R=  1                  /*remaining "      "        "     "    */
$=;       do i=Z  for N;  $= $ i;  end  /*i*/    /*populate prisoner's circle (with a #)*/
x=                                               /*the list of prisoners to be removed. */
      do c=k  by k;         p= words($)          /*keep removing until  R  are remaining*/
      if c>p then do                             /*   [↓] remove (kill) some prisoner(s)*/
                    do j=1  for words(x);      $= delword($, word(x, j) + 1 - j,   1)
                    if words($)==R  then leave c /*The slaying finished? (R people left)*/
                    end   /*j*/
                  c= (c//p) // words($);   x=    /*adjust prisoner count-off and circle.*/
                  end
      if c\==0  then x=x c                       /*the list of prisoners to be removed. */
      end   /*c*/                                /*remove 'til   R   prisoners are left.*/

say 'removing every '   th(K)   " prisoner out of "    N    ' (starting at'   Z")  with ",
                           R    ' survivor's(R)",  leaving prisoner"s(R)':'   $
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
s:  if arg(1)==1  then return arg(3);            return word( arg(2) 's', 1)   /*plurals*/
th: y= arg(1);   return y || word('th st nd rd', 1+ y // 10 * (y//100%10\==1) * (y//10<4))
output   when using the default inputs:
removing every  3rd  prisoner out of  41  (starting at 0)  with  1  survivor,  leaving prisoner:  30
output   when using the input of:     41   3   1
removing every  3rd  prisoner out of  41  (starting at 1)  with  1  survivor,  leaving prisoner:  31

{{out|output|text=  when using the input of:     41   3   1   2

removing every  3rd  prisoner out of  41  (starting at 1)  with  2  survivors,  leaving prisoners:  16 31

{{out|output|text=  when using the input of:     5   2

removing every  2nd  prisoner out of  5  (starting at 0)  with  1  survivor,  leaving prisoner:  2

Ring[edit]

n = 41
k=3
see "n =" + n + " k = " + k + " final survivor = " + josephus(n, k, 0) + nl

func josephus (n, k, m)
lm = m  
for a = m+1  to n 
     lm = (lm+k) % a 
next
josephus = lm
return josephus

Output:

n =41 k = 3 final survivor = 30

Ruby[edit]

n = (ARGV[0] || 41).to_i
k = (ARGV[1] || 3).to_i

prisoners = (0...n).to_a
prisoners.rotate!(k-1).shift  while prisoners.length > 1
puts prisoners.first

Rust[edit]

const N: usize = 41;
const K: usize = 3;
const M: usize = 3;
const POSITION: usize = 5;

fn main() {
    let mut prisoners: Vec<usize> = Vec::new();
    let mut executed: Vec<usize> = Vec::new();
    for pos in 0..N {
        prisoners.push(pos);
    }

    let mut to_kill: usize = 0;
    let mut len: usize = prisoners.len();

    while len > M {
        to_kill = (to_kill + K - 1) % len;
        executed.push(prisoners.remove(to_kill));
        len -= 1;
    }

    println!("JOSEPHUS n={}, k={}, m={}", N, K, M);
    println!("Executed: {:?}", executed);
    println!("Executed position number {}: {}", POSITION, executed[POSITION - 1]);
    println!("Survivors: {:?}", prisoners);
}
Output:
JOSEPHUS n=41, k=3, m=3
Executed: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3]
Executed position number 5: 14
Survivors: [15, 30, 34]

Scala[edit]

Executioner's Solution, not Josephus'

(Prisoners labeled 0 to n-1)

def executed( prisonerCount:Int, step:Int ) = {

  val prisoners = ((0 until prisonerCount) map (_.toString)).toList

  def behead( dead:Seq[String], alive:Seq[String] )(countOff:Int) : (Seq[String], Seq[String]) = {
    val group = if( alive.size < countOff ) countOff - alive.size else countOff
	
    (dead ++ alive.take(group).drop(group-1), alive.drop(group) ++ alive.take(group-1))
  }

  def beheadN( dead:Seq[String], alive:Seq[String] ) : (Seq[String], Seq[String]) =
    behead(dead,alive)(step)

  def execute( t:(Seq[String], Seq[String]) ) : (Seq[String], Seq[String]) = t._2 match {
    case x :: Nil => (t._1, Seq(x))
    case x :: xs => execute(beheadN(t._1,t._2))
  }

  execute((List(),prisoners))
}

val (dead,alive) = executed(41,3)
  
println( "Prisoners executed in order:" )
print( dead.mkString(" ") )
	
println( "\n\nJosephus is prisoner " + alive(0) )
Output:
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15

Josephus is prisoner 30

Seed7[edit]

The main task (find one survivor) is a special case of the extra task (find m survivors). The function executeAllButM solves the extra task and is called with m=1 to solve the main task. The function str converts an array of integer elements to a string. The function enable_output uses str to define everything necessary to write an array of integers. This way the main program can write the survivor array.

$ include "seed7_05.s7i";

const func array integer: executeAllButM (in integer: n, in integer: k, in integer: m) is func
  result
    var array integer: prisoners is [0 .. -1] times 0;
  local
    var integer: killIdx is 0;
    var integer: prisonerNum is 0;
  begin
    for prisonerNum range 0 to pred(n) do
      prisoners &:= prisonerNum;
    end for;
    writeln("Prisoners executed in order:");
    while length(prisoners) > m do
      killIdx := (killIdx + k - 1) rem length(prisoners);
      write(prisoners[killIdx] <& " ");
      ignore(remove(prisoners, killIdx));
    end while;
    writeln;
  end func;

const func string: str (in array integer: intArr) is func
  result
    var string: stri is "";
  local
    var integer: index is 0;
  begin
    for key index range intArr do
      if index <> minIdx(intArr) then
        stri &:= ", ";
      end if;
      stri &:= str(intArr[index]);
    end for;
  end func;

enable_output(array integer);
    
const proc: main is func
  begin
    writeln("Survivor: " <& executeAllButM(41, 3, 1));
    writeln("Survivors: " <& executeAllButM(41, 3, 3));
  end func;
Output:
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 
Survivor: 30
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 
Survivors: 15, 30, 34

SequenceL[edit]

Translation of: Python
main := josephus(41, 3);
    
josephus(n, k) := josephusHelper(n, k, 1, 0);

josephusHelper(n, k, i, r) :=  
        r when i > n
    else
        josephusHelper(n, k, i + 1, (r + k) mod i);
Output:
30

Sidef[edit]

Iterative:

func josephus(n, k) {
    var prisoners = @^n
    while (prisoners.len > 1) {
        prisoners.rotate!(k - 1).shift
    }
    return prisoners[0]
}

Recursive:

func josephus(n, k) {
    n == 1 ? 0 : ((__FUNC__(n-1, k) + k) % n)
};

Calling the function:

var survivor = josephus(41, 3);
say "Prisoner #{survivor} survived.";
Output:
Prisoner 30 survived.

Swift[edit]

class Josephus {
    
    class func lineUp(#numberOfPeople:Int) -> [Int] {
        var people = [Int]()
        for (var i = 0; i < numberOfPeople; i++) {
            people.append(i)
        }
        return people
    }
    
    class func execute(#numberOfPeople:Int, spacing:Int) -> Int {
        var killIndex = 0
        var people = self.lineUp(numberOfPeople: numberOfPeople)
        
        println("Prisoners executed in order:")
        while (people.count > 1) {
            killIndex = (killIndex + spacing - 1) % people.count
            executeAndRemove(&people, killIndex: killIndex)
        }
        println()
        return people[0]
    }
    
    class func executeAndRemove(inout people:[Int], killIndex:Int) {
        print("\(people[killIndex]) ")
        people.removeAtIndex(killIndex)
    }

    class func execucteAllButM(#numberOfPeople:Int, spacing:Int, save:Int) -> [Int] {
        var killIndex = 0
        var people = self.lineUp(numberOfPeople: numberOfPeople)
        
        println("Prisoners executed in order:")
        while (people.count > save) {
            killIndex = (killIndex + spacing - 1) % people.count
            executeAndRemove(&people, killIndex: killIndex)
        }
        println()
        return people
    }
}

println("Josephus is number: \(Josephus.execute(numberOfPeople: 41, spacing: 3))")
println()
println("Survivors: \(Josephus.execucteAllButM(numberOfPeople: 41, spacing: 3, save: 3))")
Output:
Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 
Josephus is number: 30

Prisoners executed in order:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 
Survivors: [15, 30, 34]

TypeScript[edit]

function josephus(n: number, k: number): number {
  if (!n) {
    return 1;
  }

  return ((josephus(n - 1, k) + k - 1) % n) + 1;
}
Output:
> josephus(41, 3);
31

Tcl[edit]

proc josephus {number step {survivors 1}} {
    for {set i 0} {$i<$number} {incr i} {lappend l $i}
    for {set i 1} {[llength $l]} {incr i} {
	# If the element is to be killed, append to the kill sequence
	if {$i%$step == 0} {
	    lappend killseq [lindex $l 0]
	    set l [lrange $l 1 end]
	} else {
	    # Roll the list
	    set l [concat [lrange $l 1 end] [list [lindex $l 0]]]
	}
    }
    return [lrange $killseq end-[expr {$survivors-1}] end]
}

Demonstrating:

puts "remaining:   [josephus 41 3]"
puts "remaining 4: [join [josephus 41 3 4] ,]"
Output:
remaining:   30
remaining 4: 3,34,15,30

VBScript[edit]

Function josephus(n,k,s)
	Set prisoner = CreateObject("System.Collections.ArrayList")
	For i = 0 To n - 1
		prisoner.Add(i)
	Next
	index = -1
	Do Until prisoner.Count = s
		step_count = 0
		Do Until step_count = k
			If index+1 <= prisoner.Count-1 Then
				index = index+1
			Else
				index = (index+1)-(prisoner.Count)
			End If
			step_count = step_count+1
		Loop
		prisoner.RemoveAt(index)
		index = index-1
	Loop
	For j = 0 To prisoner.Count-1
		If j < prisoner.Count-1 Then
			josephus = josephus & prisoner(j) & ","
		Else
			josephus = josephus & prisoner(j)
		End If
	Next
End Function

'testing the function
WScript.StdOut.WriteLine josephus(5,2,1)
WScript.StdOut.WriteLine josephus(41,3,1)
WScript.StdOut.WriteLine josephus(41,3,3)
Output:
2
30
15,30,34

Vedit macro language[edit]

This macro first creates a list of prisoners in an edit buffer.
Then the prisoners are deleted in loop until specified number of survivors are left.
When the macro finishes, you can see the list of survivors in the edit buffer.

#1 = 41		// number of prisoners
#2 = 3		// step size
#3 = 1		// number of survivors

Buf_Switch(Buf_Free)
for (#5=0; #5<#1; #5++) {
    Ins_Text("prisoner ") Num_Ins(#5, LEFT)
}

BOF
#4=1
while (#1 > #3) {
    if (#4++ % #2 == 0) {
	Del_Line(1)
        #1--
    } else {
	Line(1)
    }
    if (At_EOF) { BOF }
}
Output:
prisoner 30
Output:
when the number of survivors is set to 3
prisoner 15
prisoner 30
prisoner 34

Visual Basic .NET[edit]

Translation of: D
Module Module1

    'Determines the killing order numbering prisoners 1 to n
    Sub Josephus(n As Integer, k As Integer, m As Integer)
        Dim p = Enumerable.Range(1, n).ToList()
        Dim i = 0

        Console.Write("Prisoner killing order:")
        While p.Count > 1
            i = (i + k - 1) Mod p.Count
            Console.Write(" {0}", p(i))
            p.RemoveAt(i)
        End While
        Console.WriteLine()

        Console.WriteLine("Survivor: {0}", p(0))
    End Sub

    Sub Main()
        Josephus(5, 2, 1)
        Console.WriteLine()
        Josephus(41, 3, 1)
    End Sub

End Module
Output:
Prisoner killing order: 2 4 1 5
Survivor: 3

Prisoner killing order: 3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
Survivor: 31

V (Vlang)[edit]

Translation of: Go
// basic task fntion
fn final_survivor(n int, kk int) int {
    // argument validation omitted
    mut circle := []int{len: n, init: it}
    k := kk-1
    mut ex_pos := 0
    for circle.len > 1 {
        ex_pos = (ex_pos + k) % circle.len
		circle.delete(ex_pos)
    }
    return circle[0]
}
 
// extra
fn position(n int, kk int, p int) int {
    // argument validation omitted
    mut circle := []int{len: n, init: it}
    k := kk-1
	mut pos := p
    mut ex_pos := 0
    for circle.len > 1 {
        ex_pos = (ex_pos + k) % circle.len
        if pos == 0 {
            return circle[ex_pos]
        }
        pos--
		circle.delete(ex_pos)
    }
    return circle[0]
}
 
fn main() {
    // show basic task fntion on given test case
    println(final_survivor(41, 3))
    // show extra fntion on all positions of given test case
    println("Position  Prisoner")
    for i in 0..41 {
        println("${i:5}${position(41, 3, i):10}")
	}
}
Output:
30
Position  Prisoner
    0         2
    1         5
    2         8
    3        11
    4        14
    5        17
    6        20
    7        23
    8        26
    9        29
   10        32
   11        35
   12        38
   13         0
   14         4
   15         9
   16        13
   17        18
   18        22
   19        27
   20        31
   21        36
   22        40
   23         6
   24        12
   25        19
   26        25
   27        33
   28        39
   29         7
   30        16
   31        28
   32        37
   33        10
   34        24
   35         1
   36        21
   37         3
   38        34
   39        15
   40        30

Wren[edit]

Translation of: Kotlin
var josephus = Fn.new { |n, k, m|
    if (k <= 0 || m <= 0 || n <= k || n <= m) Fiber.abort("One or more parameters are invalid.")
    var killed = []
    var survived = List.filled(n, 0)
    for (i in 0...n) survived[i] = i
    var start = k - 1
    while (true) {
        var end = survived.count - 1
        var i = start
        var deleted = 0
        while (i <= end) {
            killed.add(survived.removeAt(i-deleted))
            if (survived.count == m) return [survived, killed]
            deleted = deleted + 1
            i = i + k
        }
        start = i - end - 1
    }
    return [survived, killed]
}

var triples = [ [5, 2, 1], [41, 3, 1], [41, 3, 3] ]
for (triple in triples) {
    var n = triple[0]
    var k = triple[1]
    var m = triple[2]
    System.print("Prisoners = %(n), Step = %(m), Survivors = %(m)")
    var sk = josephus.call(n, k, m)
    System.print("Survived   : %(sk[0])")
    System.print("Kill order : %(sk[1])")
    System.print()
}
Output:
Prisoners = 5, Step = 1, Survivors = 1
Survived   : [2]
Kill order : [1, 3, 0, 4]

Prisoners = 41, Step = 1, Survivors = 1
Survived   : [30]
Kill order : [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15]

Prisoners = 41, Step = 3, Survivors = 3
Survived   : [15, 30, 34]
Kill order : [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3]

XPL0[edit]

include c:\cxpl\codes;

func Prisoner(N, K);            \Return final surviving prisoner
int  N, K;                      \number of prisoners, number to skip
int  I, J;
char A;
[A:= Reserve(N);
for I:= 0 to N-1 do A(I):= I;
I:= 0;
repeat  I:= I+K-1;                              \skip to next prisoner
        I:= rem(I/N);                           \wrap to start if necessary
        IntOut(0, A(I)); ChOut(0, ^ );          \show killed prisoner
        for J:= I to N-2 do A(J):= A(J+1);      \shift survivors down
        N:= N-1;                                \one less prisoner
until   N=1;
return A(0);
];

[IntOut(0, Prisoner(5, 2));  CrLf(0);
 IntOut(0, Prisoner(41, 3));  CrLf(0);
]
Output:
1 3 0 4 2
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30

zkl[edit]

Translation of: Julia
fcn j(n,k){
   reg p=[0..n-1].walk().copy(), i=0, seq=L();
   while(p){
      i=(i+k-1)%p.len();
      seq.append(p.pop(i));
   }
   "Prisoner killing order: %s.\nSurvivor: %d"
   .fmt(seq[0,-1].concat(","),seq[-1]);
}
Output:
j(41,3).println();
Prisoner killing order: 2,5,8,11,14,17,20,23,26,29,32,35,38,0,4,9,13,18,22,27,31,
            36,40,6,12,19,25,33,39,7,16,28,37,10,24,1,21,3,34,15.
Survivor: 30
fcn j2(n,k,m){
   reg p=[0..n-1].walk().copy(), i=0, seq=L();
   while(p.len()>m){
      i=(i+k-1)%p.len();
      seq.append(p.pop(i));
   }
   "Prisoner killing order: %s.\nSurvivors: [%s]"
   .fmt(seq.concat(","),p.concat(","))
}
Output:
j2(41,3,3).println();
Prisoner killing order: 2,5,8,11,14,17,20,23,26,29,32,35,38,0,4,9,13,18,22,27,
          31,36,40,6,12,19,25,33,39,7,16,28,37,10,24,1,21,3.
Survivors: [15,30,34]

ZX Spectrum Basic[edit]

Translation of: ANSI Standard BASIC
10 LET n=41: LET k=3: LET m=0
20 GO SUB 100
30 PRINT "n= ";n;TAB (7);"k= ";k;TAB (13);"final survivor= ";lm
40 STOP 
100 REM Josephus
110 REM Return m-th on the reversed kill list; m=0 is final survivor.
120 LET lm=m: REM Local copy of m
130 FOR a=m+1 TO n
140 LET lm=FN m(lm+k,a)
150 NEXT a
160 RETURN 
200 DEF FN m(x,y)=x-INT (x/y)*y: REM MOD function