- Historian Flavius Josephus (37-93+AD) was a controversial
writer/historian who chronicled the onslaught of the Romans against the
Jewish people of his time.

- One story attributed to him by Arthur Engle,
though I haven't authenticate it, has him leading a group of 40 jews who, caught in a cave by the Romans, choose death over
slavery. As the story goes, it was decided (by Josephus?) that the
40 would line up (hap hazardly?) in a circle at starting at some (random?)
point and counting around the circle, every seventh person would be killed,
shortening the circle as they progressed. It was agreed that the
last survivor would commit suicide. As the chronicler of the story
(Josephus) has it, the only survivor was (by coincidence?) Josephus.
Josephus decided to "live to fight again," and enter the servitude of the
Roman conqueror Titus, instead.

Did Josephus actually experience this? - and if he did, did he solve the problem of the last survivor beforehand? In what follows we examine the Josephus problem and discover how to find

- I have written a program for the TI-85 which returns the number of
the survivor,

The TI program I wrote is pretty blunt. It creates a list of n complex numbers whose real part indicates their position in the circle and whose imaginary part is 0 if they're alive and 1 if they're dead. It then steps around the circle killing every kth live object until all but one are dead.

While there are many improvements that can be made to my TI program,
TI basic is not able to come close to the efficiency of the following Pascal
program found in Engel's book:

**begin**

**if **n<3 **then** f := 1
// if n is 1 or 2, the survivor is 1

**else if** odd(n) **then
**// if n is odd, then the survivor on the inner
circle is

f := 2*f(n div 2)+1
// whereas, if n is even then the survivor is

**else **f := 2*f(n div 2)-1 //
Note that "n div 2" is the integer part of n/2.
**end;**

**begin**

write('n='); readln(n);
// This is the main part of the program

writeln(f(n)); readln
**end.**

f(12) = 2*f(6)-1 = 2*(2*f(3)-1)-1 = 2*(2*(2*f(1)+1)-1)-1
(expansion)

= 2*(2*(2*1+1)-1)-1
= 2*(2*(3)-1)-1 = 2*(5)-1 = 9 (contraction)

Let's justify that this recursive scheme gives the
solution to the . And . . .rather than people being killed; which
has become a tiresome premise, let's assume we're talking about blue balls
turning red when their numbers come up.

If there is an even number, 2n*,* of
blue balls in the circle and all the even numbered balls turn red, after
which we renumber the ducks: then duck number 2n* *- 1 is renumbered
duck n. Thus the original number of the survivor* *f(n) on the
smaller circle was numbered f(2n) = 2f(n) - 1 (see the picture on
the left below.)

If there is an odd number, 2n+1, of blue balls in
the circle and every other one turns red (again, the even-numbered ones
- but this time duck number 1 also flies away,) after which the remaining
ducks a renumbered - then the original number of the survivor*
f*(*n*) on the smaller, inner circle is *f*(*2n+*1) *=
2f*(*n*)*+*1.

All of this suggests that, even though the TI-Basic language doesn't
accomodate the slick recursion features of Turbo Pascal 7.0 from Borland,
we could simulate the process by dividing n by 2 and putting a 1 or -1
into a list, depending on whether the resulting number is even or odd (expansion)
and then using the list to construct f(n) by starting with 1 and doubling
with an addition or subtraction of 1 a number of times (contraction.)

- Engel gives the the following Pascal code for an
algorithm which produces the number,

**begin**

write('n,k,i=');

readln(n,k,i);

x := k*i;

**while **x>n **do**

x := int((k*(x-n)-1)/(k-1));

writeln('the ', i : 0 : 0, '-th elim. person has
#', x : 0 : 0);

readln
**end.**

Define the j-th count of a ball to be

So if there are n = 5 blue balls originally and every
third blue ball is turned red (k = 3) then the fourth ball survives and
will have the sequence {*x*_{1}=4, *x*_{2}=8,
*x*_{3}=11} while the sequence for the
first ball is {1, 6}

If the ball *x*_{1}
has not turned red on round j+1, then
* *
(1)*
x*_{j+1} = *x*_{j}
+ *n* - floor(*x*_{j}/*k*).

Here "floor" means "the greatest integer less than." To see that
this is so, observe that the number of red balls on the *j*-th
round is floor(*x*_{j}/*k*), so
the number remaining is *n* - floor(*x*_{j}*/k*)
and adding this number to the previous count gives the next count.

Now *x*_{j}/*k*
= floor(*x*_{j}*/k*) + r/k, where
the remainder, 1/k<= r/k<= (k-1)/k. Note that the remainder
can't be 0 or the ball would be turned red. Solving for floor(*x*_{j}*/k*)
and substituting into equation (1) we get

*
x*_{j+1} = *x*_{j}
+ *n* - *x*_{j}/*k
+ r/k = n + r/k + x*_{j}(1 - 1/*k*)
*<=> x*_{j}
= (*x*_{j+1} - *n* *- r*/*k*)**k/*(*k-*1)
= (*x*_{j+1} - *n*)**k/*(*k-*1)
- *r*/(*k-*1)

If this last term were sure to be less than 1 we
could take the integer part of the first term and thus have a formula we
could follow backwards to find the original *x*_{1
}, but if r=k-1 this doesn't work So borrow 1/(k-1)
from the first term:

* x*_{j}
= [(*x*_{j+1}* -* *n*)**k
- *1]*/*(*k-*1) - (*r-*1)/(*k-*1) = floor( [(*x*_{j+1}*
-* *n*)**k - *1]*/*(*k-*1) )

Or, by subtracting and adding (*x*_{j+1}*
-* *n*)*/*(*k-*1), we have

*x*_{j}
= floor( [(*x*_{j+1}* -* *n*)*(*k-*1)
*+ x*_{j+1}* - n - *1]*/*(*k-*1)
) and finally,

(2)
*x*_{j} = *x*_{j+1}*
-* *n + *floor( (*x*_{j+1}*-n-*1)*/*(*k-*1)
)

Now, if* x*_{j} is divisible
by *k *then the ball turns red and the sequence {*x*_{j}}
terminates. At that point the ball becomes the (*x*_{j}/*k*)-th
red ball, thus the last count of the* i*-th red ball is *x*_{j}
=* i***k*. So we start with this value and iterate back
to the original *x*_{1 } using (2).

If you have comments or suggestions,
email me.