/* Programmer: Bill Marion
   Date: 2/14/06
   Modified: 2/16/06   
*/
 
/* Import the simple standard I/O classes developed by Prof. Greg Hume. */ 

import hsa.*;

/* Statement of Problem: Suppose n objects are arranged in a circle (n >= 1)
   and are numbered from 1 to n, say clockwise. Starting with object number 1 
   and counting each object in turn around the circle, remove every mth object
   until there is only one object left. Determine the number of the object
   remaining. (Ball and Coexeter, 1987; Tanenbaum and Aygenstein, 1977;
   Woodhouse, 1977) 
   
   The following recursive definition, written as a function of n and m, 
   provides us with a solution.
   
   J(n,m) = (J(n-1,m) + m) mod n, for n >= 2,
   with the initial condition, J(n,m) = 1, for n = 1. */
   
/* This computational solution computes J(n,m) for all integers n and m >= 1.
   It does so by renumbering the objects from 0 to n-1, computing the solution
   using the above recursive defintion with the adjusted intial condition
   J(n,m) = 0, for n = 1, and, then, adding 1 to the number of the object
   returned. */
   
       

class JosephusProblem
{
  static int josephusPrime(int n, int m)
  {
    int number = 0;
    
    if (n == 1)
      number = 0;
    else 
      number = (josephusPrime(n-1,m) + m) % n;
      
    return number;
    
  } // end josephusPrime
  
  static public void main(String[] args)
  {
    Stdout.println();
    Stdout.print("Enter the number of objects in the circle--enter 0");
    Stdout.println(" to stop.");
    int numberOfObjects = Stdin.readInt();
    
    while (numberOfObjects >= 1)
    {
      Stdout.println();
      Stdout.print("Enter the number representing the removal of every mth");
      Stdout.println(" object");
      int numberOfRemoval = Stdin.readInt();
      Stdout.println();
    
      int numberLeft = josephusPrime(numberOfObjects, numberOfRemoval) + 1;
    
      Stdout.print("The number of the last object remaining is: ");
      Stdout.println(numberLeft);
      Stdout.println();
      
      Stdout.print("Enter the number of objects in the circle--enter 0");
      Stdout.println(" to stop.");
      numberOfObjects = Stdin.readInt();
    }
    
    Stdout.println();
  } // end main
} // end JosephusProblem