And his problem was big - like a life or death one. So the Jewish-Roman war was ongoing and he was trapped with 41 jewish rebels. And they didn't want to get captured. So what do you do then?... You decide to kill yourself. Luckily our guy didn't swing their way and decided to survive.
Well, the rebels decided to round up in a circle and kill every 2th(or was it 3th, whatever) person until no one has left. The trick was that the last one had to kill himself and thus if Joseph wanted to survive he had to be that person. Of course Joseph had a common lisp read-eval-print loop and wrote the following to get the spot of the survivor:
(defun kill-ring (l n)
(let ((res '()) (kill 1))
(dolist (x l)
(if (eql kill n)
(setf kill 1)
(funcall
(lambda ()
(setf kill (+ kill 1))
(setf res (append res (list x)))))))
;; Also, print steps, I'm lazy
(print res)
(if (< (length res) n)
res
(setf res (kill-ring res n)))))
So naturally he entered something like:
(kill-ring '(1 2 3 4 5) 2)
and got the answer (1) BUT what I forgot to tell you is that the killing persisted(and did not began from the start every time). What this means is that if we have (1 2 3 4 5) and have to kill every 2th person we will go: 2, 4, 1, 5, therefore 3 is the right place to be. And he decided that it is a good time to modify:
(defun kill-ring-cycle (l n &optional (offset 0))
(let ((res '()) (kill (+ 1 offset)) (last-kill 0) (i 0))
(dolist (x l)
(if (eql kill n)
(and (setf kill 1)
(setf last-kill i))
(funcall
(lambda ()
(setf kill (+ kill 1))
(setf res (append res (list x))))))
(setf i (+ 1 i)))
(let ((off (- n (- n (- (length l) (+ last-kill 1))))))
(if (< (length res) n)
res
(setf res (kill-ring-cycle res n off))))))
Yet again he faced the limitations of his time - general purpose mechanical computing was expensive and slow, machine cycles were precious, his time alive - not that much so he can waste it. And if the story did sound at least a little consistent by far we can deduce that Joseph was reasonably smart. As a consequence he used mathematical induction to optimize his function.
First, he catched a pattern - the number that survived was always odd. Why? Well, because on the first iteration we "kill" every single one that is not odd(and yes - this is a great pun). Next, he got that we have three distinctive cases - n (half of people in the circle) is 1, is an even number or an odd number. We can produce the following open formulas( this time in python):
1. For n = 1
case1 = lambda: 1
2. For 2n people(even) we can do something for n = 5 and then produce all derivatives(in fact we can do more, but it doesn't matter at this stage)
case2 = lambda n: 3 if n == 5 else 2*case2(n/2)-1
3. For 2n+1 people(odd) we do a similar thing(again not fully functional)
case3 = lambda n: 3 if n == 5 else 2*case3((n-1)/2)+1
Now is a good time to unfold part of our brain potential and transform the above to a closed form so that we can save our guy from getting killed(thus resulting in him getting a shorter wiki page). So through observing pairs of n->X where X is the surviving number we can deduce that the whole thing can be presented in the form for every 2th person(here is the whole thing):
(defun kill-ring-optimzed-cycle (N)
(+ (* 2 (- n (expt 2 (truncate (log N 2))))) 1))It is good to point out that this is a work of fiction and Joseph might not really needed to use an interpreter(some other stuff might not be true too)