Problem Statement

Josephus problem is a math puzzle with a grim description:

n

{\displaystyle n}

prisoners are standing on a circle, sequentially numbered from

0

{\displaystyle 0}

to

n − 1

{\displaystyle n-1}

.
An executioner walks along the circle, starting from prisoner

0

{\displaystyle 0}

, removing every

k

{\displaystyle k}

-th prisoner and killing him.
As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. > For example, if there are

n

5

{\displaystyle n=5}

prisoners and

k

2

{\displaystyle k=2}

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

Given any

n , k

0

{\displaystyle n,k>0}

,   find out which prisoner will be the final survivor.
In one such incident, there were 41 prisoners and every 3rd prisoner was being killed   (

k

3

{\displaystyle k=3}

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

The captors may be especially kind and let

m

{\displaystyle m}

survivors free, and Josephus might just have

m − 1

{\displaystyle m-1}

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

Let's start with the solution:

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