4
$\begingroup$

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); 
  • 0
    i think your equation is missing a constant. `return ((f($n-1, $k) + $k - 1) % $n + 1);`2013-09-05

1 Answers 1

2

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.

  • 0
    Thanks! That was actually quite helpful and I have it all working now, without my brain hurting.2012-04-11