Stepping through the Josephus problem

Question

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);

Answer 1

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.