; Program: The Josephus Problem
; Solution: By Kathryn Shafer and Bill Marion; modified
; by Bill Marion (2/10/06)

; Statement of the Problem: Suppose n objects are arranged in 
; a circle (n >= 1) and are numbered from 1 to n, say clockwise.
; Starting with object number 1 and counting each object in turn 
; around the circle, remove every mth object until there is only
; one object left. Determine the number of the object remaining.
; (Ball and Coexeter, 1987; Tanenbaum and Augenstein, 1977; 
; Woodhouse, 1978)

; The following recursive definition, written as a function of n
; and m, provides us with the solution.
;            
; J(n,m) = (J(n-1,m) + m)mod n, for n >= 2.
; with the initial condition, J(n,m) = 1, for n = 1.

; This computational process asks the user repeatedly to input the number 
; of objects in the circle, n, (0 to quit), and, if n >= 1, asks for the
; number representing every mth object to be removed, calls the function
; to compute the number of the object remaining and displays that number.

(define josephus-problem
  (lambda ()
    (newline)
    (display "Enter the number of objects in the circle--or 0 to quit")
    (newline)
    (let ((n (read)))
      (if (= n 0)
          (begin
            (newline)
            (display "finished")
            (newline))
          (begin
            (display "Enter the number representing every mth object to be removed") 
            (newline)
            (let ((m (read))) 
            (let ((objectLeft (josephus n m)))
            (newline)
            (display "The number of the object remaining is: ")
            (display objectLeft)
            (newline)
            (josephus-problem))))))))
    
; This computational process computes J(n,m) for all integers n and
; m >= 1. It does so by renumbering the n objects from 0 to n-1, 
; computing the solution using the above recursive definition with the
; adjusted initial condition J(n,m) = 0, for n = 1, and, then, adding 1 
; to the number of the object returned.

(define josephus
  (lambda (n m)
    (+ 1 (josephus-prime n m))))

(define josephus-prime
  (lambda (n m)
    (if (= n 1)
        0
        (remainder (+ (josephus-prime (- n 1) m) m) n))))