Can someone please explain the use of modulus in this code?

Question

I know that modulus gives the remainder and that this code will give the survivor of the Josephus Problem. I have noticed a pattern that when n mod k = 0, the starting count point begins at the very beginning of the circle and that when n mod k = 1, the person immediately before the beginning of the circle survived that execution round through the circle.

I just don't understand how this recursion uses modulus to find the last man standing and what josephus(n-1,k) is actually referring to. Is it referring to the last person to get executed or the last survivor of a specific round through the circle?

 def josephus( n, k):
  if n ==1:
    return 1
  else:
    return ((josephus(n-1,k)+k-1) % n)+1

Answer 1

This answer is both a summary of the Josephus Problem and an answer to your questions of:

1. What is josephus(n-1,k) referring to?
2. What is the modulus operator being used for?

When calling josephus(n-1,k) that means that you've executed every kth person up to a total of n-1 times. (Changed to match George Tomlinson's comment)

The recursion keeps going until there is 1 person standing, and when the function returns itself to the top, it will return the position that you will have to be in to survive. The modulus operator is being used to help stay within the circle (just as GuyGreer explained in the comments). Here is a picture to help explain:

 1 2
6   3
 5 4

Let the n = 6 and k = 2 (execute every 2nd person in the circle). First run through the function once and you have executed the 2nd person, the circle becomes:

 1 X
6   3
 5 4

Continue through the recursion until the last person remains will result in the following sequence:

 1 2      1 X      1 X      1 X      1 X      X X
6   3 -> 6   3 -> 6   3 -> X   3 -> X   X -> X   X
 5 4      5 4      5 X      5 X      5 X      5 X

When we check the values returned from josephus at n we get the following values:

n = 1 return 1
n = 2 return (1 + 2 - 1) % 2 + 1 = 1
n = 3 return (1 + 2 - 1) % 3 + 1 = 3
n = 4 return (3 + 2 - 1) % 4 + 1 = 1
n = 5 return (1 + 2 - 1) % 5 + 1 = 3
n = 6 return (3 + 2 - 1) % 6 + 1 = 5

Which shows that josephus(n-1,k) refers to the position of the last survivor. (1)

If we removed the modulus operator then you will see that this will return the 11th position but there is only 6 here so the modulus operator helps keep the counting within the bounds of the circle. (2)

Answer 2

Your first question has been answered above in the comments.

To answer your second question, it's referring to the position of the last survivor.

Consider j(4,2).

Using the algorithm gives

j(4,2)=(j(3,2)+1)%4)+1  
j(3,2)=(j(2,2)+1)%3)+1  
j(2,2)=(j(1,2)+1)%2)+1  
j(1,2)=1 

and so

j(2,2)=((1+1)%2)+1=1  
j(3,2)=((1+1)%3)+1=3  
j(4,2)=((3+1)%4)+1=1 

Now the table of j(2,2) is

1 2  
1 x

so j(2,2) is indeed 1.

For j(3,2) we have

1 2 3  
1 x 3  
x x 3  

so j(3,2) is 3 as required.

Finally, j(4,2) is

1 2 3 4  
1 x 3 4  
1 x 3 x  
1 x x x  

which tells us that j(4,2)=1 as required.