# Stepping through the Josephus problem

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);  - There's an extensive and accessible discussion of this problem in the first chapter of Concrete Mathematics by Graham, Knuth, and Patashnik. – MJD Mar 30 '12 at 8:34 Note that I've cleaned up some inconsistencies in the Wikipedia article since the question was posted. – joriki Mar 30 '12 at 11:22 @JoshB There was a question on similar topic at snipurl.com/22u8sam (not sure if relevant) – Kirthi Raman Mar 30 '12 at 12:02 You might be interested in this, this and this. – draks ... Mar 30 '12 at 13:32 i think your equation is missing a constant. return ((f($n-1, $k) +$k - 1) % $n + 1); – DevZer0 Sep 5 '13 at 3:01 ## 1 Answer The Wikipedia article was rather confused on whether the indices start at$0$or$1$and on whether the first person killed is the first or the$k$-th person; I've cleaned it up. You don't state exactly what problem you're dealing with (which is generally a bad idea). The formulas you give are correct for indices starting at$0$, but the numbers in the Wikipedia section for$k=2$that you're comparing with are for indices starting at$1$. Your recurrence is correct for indexing from$0$. When you posted the question, the recurrence in the Wikipedia article was incorrect since it gave the same recurrence despite otherwise indexing from$1\$; I've fixed that.

-
Thanks! That was actually quite helpful and I have it all working now, without my brain hurting. – Josh B Apr 11 '12 at 7:55