How to find "the first survivor" after a given position in the Josephus puzzle?

Question

I want to find the next survivor after a given position and number of people.

(define renumber
 (lambda (position n)
(if (< position 3)
        (+ position (- n 3))
        (- position 3))))



(define survives?
  (lambda (position n)
    (if (< n 3)
    #t
    (if (= position 3)
        #f
    (survives? (renumber position n) (- n 1))))))


(define first-survivor-after
(lambda (position n)
  (cond ((and (<= n 3)(<= position 3)) null)
        ((or (>= n 3)(>= position 3))(survives? position n)
             (if = #f survives?)
                (survives? (+ 1 position) n)
                "Surviving position"))))

I just need to replace the last bit there with the exact number of the surviving position. The program will run until it finds the survivor, I just don't know how to give the position as an answer since now everything is in terms of true and false. Thank you!

Answer 1

Your algorithm doesn't seem correct, and there are syntax errors. For example, this condition is plain wrong: (if = #f survives?). That's not how you write an if expression in Scheme - perhaps you meant (if (equal? (survives? position n) #f) ...). Start by getting the basics right!

In Wikipedia you'll find a fine explanation of the solution, together with a couple of implementations, which should be easy to write in Scheme. Just for fun, here's my take on an efficient tail-recursive solution, using a named let:

(define (first-survivor-after position n)
  (let loop ([i   1]
             [acc 0])
    (if (> i n)
        (add1 acc)
        (loop (add1 i)
              (modulo (+ acc position) i)))))

Or equivalently, a non-tail-recursive version using a helper procedure:

(define (first-survivor-after position n)
  (define (loop i)
    (if (= i 1)
        0
        (modulo (+ (loop (sub1 i)) position) i)))
  (add1 (loop n)))