Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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);
share|improve this question
    
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 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.