I'm trying to figure out how the math in the Josephus problem works exactly. I first heard of it for programming purposes so that's where my focus has been. The formula does seem to be recursive from what I can tell, and that's what's been killing me in solving it out by hand for any value of n or k.
f(n,k) = (f(n-1,k)+k) mod n
That one comes with the additional part that:
f(1,k)=0
Using that I've written a few out by hand but I always get zero for the answer, even when using k=2 so I can test my results against the ones in the Wikipedia article.
f(2,2)=(f(1,2)+2)%2
Now since n=1 it returns 0 at this point so I get this:
f(2,2)=((0)+2)%2
Which of course is 0, when the answer to that one should be 1. Any idea what I'm missing on that one, and how would I expand this out to incorporate any value of k? I attempted to write this in perl, however that returns about the same values I've been getting by hand, so I'm not quite sure where my logic is failing.
#!/usr/bin/perl use strict; use warnings; sub f { my ($n, $k) = @_; if ($n == 1) { return 0; } else { return ((f($n-1, $k) + $k) % $n); } } sub main { my ($n, $k) = @_; my $result = f($n,$k); print "With $n soldiers and killing every $k" . "'th, the safe spot is $result\n"; } main(@ARGV);