/*
 * Main.java
 *
 * Created on February 11, 2008, 12:42 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package hanoi;

/**
 *
 * @author suchenek
 */
public class Main {
    
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
  
   
 static int count = 0;
 	public static void main (String [] args)
 	{int disks;
         disks=15;
//  		int disks = Integer.parseInt(args[0]);
		Move(1, 3, disks);
		System.out.println("Total number of moves: " + count + " ");
                System.out.println(((int)Math.pow(2,disks)-1) + " = 2^" + disks + " - 1");
	 }
 
 	public static void Move(int source, int target, int disks)
	 {
 			
 		if (disks != 0) 
 		{
 			int aux = 6 - (source + target);
 			Move(source, aux, disks-1);
 			System.out.println("Disk " + disks + " moved from peg" +
 				source + " to peg" + target);
                        count++;
 			Move(aux, target, disks-1);
 		}
 	}
 
 
}
//
// Recurrence relation:
//
// (1)  T(0) = 0
//        
// T(n) = T(n-1) + 1 + T(n-1) = 2*T(n-1) + 1
//
//or:
//
// (2) T(n) = 2*T(n-1) + 1
//
// Solution
//
// T(n) = 2^n - 1
// 
//
// Proof
//
// Substitute 2^n - 1 for T(n) in (1) and (2)
//
// Check that equation (1) is satisfied:
//
// L(0) = 2^(0) - 1 = 1 - 1 = 0 = R(0) 
//
// So, L(0) = R(0) OK
//
// Check that equation (2) is satisfied:
//
// R(n) = 2*(2^(n-1) - 1) + 1 = 2*2^(n-1) - 2 + 1 = 2^n - 1 = L(n)
//
// So, L(n) = R(n) OK
// 
// So, T(n) = 2^n - 1
//
// This completes the proof
// 
// Example
// 
// n = 6 count = 63
// 2^6 - 1 = 64 -1 = 63. Bingo!
//