# Josephus' Puzzle Basic Java with some basic math.

So I was trying to write a little java program that would solve [Josephus' Problem][1]. The one where you have a certain amount of people in a circle and then a count where every 3rd, 4th or what have you is eliminated, until there is only one remaining. I was writting a program that will take user input for the number of soldiers as well as the count between each kill.

Heres a link to the problem in more detail:

http://en.wikipedia.org/wiki/Josephus_problem

Using this logic.

Assuming that the start position is index 1. He is safe as he is the only one in the game:

f(1,k) = 1

In general you solve the nth case by reducing the problem by 1 and solving, adding k afterwards:

f(n,k) = f(n-1,k)+ k mod n+1
= f(n-2,k) + 2k mod n
= f(1,k) + (n-1)k mod n
= 1 + (n-1)k mod n

Should be: return 1 + (((n-1) * k) % n);

I came up with this.

import java.util.Scanner;

public class JosephusProblem
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);

int safespace;
System.out.println("Please enter the number of soliders");
int soldiers = input.nextInt();
System.out.println("Please enter the how many soldiers are skipped before the next death");
int count = input.nextInt();
//safespace = 1 + (((soldiers-1) * count) % soldiers);
safespace = 1 + (((count-1) * soldiers) %count);
System.out.println("The safe place to stand would be " + safespace);
}
//end main
}
//end class


At first I thought it was just a stupid mistake of me getting the variables mixed up (as you can see) but neither is returning what I was looking for. Math is not my strong suit and this has been bugging me for a little longer than I like. Can anyone tell me where I went wrong? Thank you in advance for any adive you can give!

-

First when you look at the algorithm \begin{align*} f(n,k) &= \left(f(n-1,k)+ k \right) ({\text mod} n) + 1\\ &= \left(f(n-2,k) + 2k \right) ({\text mod} n) +1\\ &= \left(f(1,k) + (n-1)k \right) ({\text mod} n) \\ &= 1 + (n-1)k ({\text mod} n) \\ \end{align*} is not correct They are not always mod $n$ When you find $f(n-1, k)$ it goes like this
$$f(n-1, k) = \left(f(n-2, k)+ k\right) ({\text mod}\hspace{3pt} (n-1))$$