import java.text.NumberFormat;
import java.math.BigInteger;

public class Hailstone extends Object
{

  private static NumberFormat nf = NumberFormat.getInstance();
  private static final BigInteger TWO = BigInteger.ONE.add( BigInteger.ONE );
  private static final BigInteger THREE = TWO.add( BigInteger.ONE );


  public static void main(String args[])
  {
    long unity = 1;
    long loopLimit = 1;
    long loopOffset = 0;
    long loopIndex;
    long loopHighest;
    long bigintLoops = 0;
    long generalHighestValue = 0;
    long generalHighestStepCount = 0;
    long value;
    long topper;
    long stepCount;
    BigInteger biGeneralHighestValue = BigInteger.ZERO;
    boolean equalledHighestValue;
    boolean equalledHighestStepCount;
    boolean improvedHighestValue;
    boolean improvedHighestStepCount;

    topper = ( (long) 1 ) << 60;

    switch ( args.length )
    {
      case 0:
        usage();  // exits
      case 4:
        generalHighestStepCount = ( new Long( args[2] ) ).longValue();
        biGeneralHighestValue = biParse( args[3] );
        if ( biGeneralHighestValue.toString().length() > 18 )
        {
          generalHighestValue = ( 3 * topper ) + 2;  // push out of reach
        }
        else
        {
          generalHighestValue = biGeneralHighestValue.longValue();  // share
        }
      case 2:
        loopOffset = ( new Long( args[1] ) ).longValue();
        // Cheat a bit since we already know, from testing, the first starting
        // point to push the calculation into using BigInteger arithmetic.
        if ( loopOffset >= 319804831 )
        {
          generalHighestValue = ( 3 * topper ) + 2;  // push out of reach
        }
      case 1: 
        loopLimit = ( new Long( args[0] ) ).longValue();
        break;
      default:
        usage();  // exits
    }

    System.out.println
    (
      "Running Hailstone with parms: "
      + loopLimit
      + (
          ( args.length > 1 )
          ? " " + loopOffset
          : ""
        )
      + (
          ( args.length > 3 )
          ? " "
            + generalHighestStepCount
            + " "
            + biGeneralHighestValue.toString()
          : ""
        )
    );

    loopIndex = 0;
    while ( loopIndex < loopLimit )
    {
      loopIndex++;
      loopHighest = 0;
      stepCount   = 0;
      equalledHighestValue = false;
      equalledHighestStepCount = false;
      improvedHighestValue = false;
      improvedHighestStepCount = false;
      value = loopIndex + loopOffset;

      while ( value != 1 && value < topper )
      {
	if ( ( value & ( (long) 1 ) )  == (long) 0 )
	{
	  value >>= 1;
	}
	else
	{
	  value = ( value << 1 ) + value + (long) 1;

          if ( value > loopHighest ) { loopHighest = value; }

	}
	stepCount++;
/*
	System.out.println
	(
	  "  start "
          + nf.format( loopIndex + loopOffset )
          + ", current "
          + nf.format( value )
          + ", step "
	  + nf.format( stepCount )
	);
*/
      }

      if ( loopHighest <= topper )
      {

        if ( stepCount == generalHighestStepCount )
        {
          equalledHighestStepCount = true;
        }

        if ( loopHighest == generalHighestValue )
        {
          equalledHighestValue = true;
        }

        if ( loopHighest > generalHighestValue )
        {
          improvedHighestValue = true;
          generalHighestValue = loopHighest;
          biGeneralHighestValue = BigInteger.valueOf( generalHighestValue );
        }

        if ( stepCount > generalHighestStepCount )
        {
          generalHighestStepCount = stepCount;
          improvedHighestStepCount = true;
        }

        if ( equalledHighestStepCount == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " equalled the highest step count at "
             + nf.format( generalHighestStepCount )
             + " -  -  -  -  -  -  -  -"
             + " reaching a peak value of "
             + nf.format( loopHighest )
          );
        }

        if ( improvedHighestStepCount == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " improved the highest step count to "
             + nf.format( generalHighestStepCount )
             + " -  -  -  -  -  -  -  -"
             + " reaching a peak value of "
             + nf.format( loopHighest )
          );
        }

        if ( equalledHighestValue == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " equalled the highest value seen at "
             + nf.format( generalHighestValue )
             + " -  -  -  -  -  -  -  -"
             + " using "
             + nf.format( stepCount )
             + " steps"
          );
        }

        if ( improvedHighestValue == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " improved the highest value seen to "
             + nf.format( generalHighestValue )
             + " -  -  -  -  -  -  -  -"
             + " using "
             + nf.format( stepCount )
             + " steps"
          );
        }

      }
      else
      {
/*
** Do it with BigIntegers instead, but only for the overflow cases!
*/

        bigintLoops++;

        generalHighestValue = ( 3 * topper ) + 2; // make it unreachable

/*
	System.out.println
	(
          "overflow occurred at start "
	  + nf.format( loopIndex + loopOffset )
          + ", step "
	  + nf.format( stepCount )
          + ", value " 
	  + nf.format( loopHighest )
	);
*/

	/* System.exit(1); */

        stepCount   = 0;
        equalledHighestValue = false;
        equalledHighestStepCount = false;
        improvedHighestValue = false;
        improvedHighestStepCount = false;

	BigInteger biLoopHighest = BigInteger.ZERO;
	BigInteger biValue = BigInteger.valueOf( loopIndex + loopOffset );

        while ( biValue.compareTo( BigInteger.ONE ) != 0 )
        {
          if ( biValue.compareTo( biValue.clearBit( 0 ) ) == 0 )
          {
            biValue = biValue.shiftRight( 1 );  // divide by two
          }
          else
          {
            biValue = biValue.multiply( THREE );
            biValue = biValue.add( BigInteger.ONE );

            if ( biValue.compareTo( biLoopHighest ) > 0 )
            {
              biLoopHighest = biValue;
            }

          }
          stepCount++;
/*
          System.out.println
          (
            "  start "
            + nf.format( loopIndex + loopOffset )
            + ", current "
            + nf.format( value )
            + ", step "
            + nf.format( stepCount )
          );
*/
        }

        if ( stepCount == generalHighestStepCount )
        {
          equalledHighestStepCount = true;
        }

        if ( biLoopHighest.compareTo( biGeneralHighestValue ) == 0 )
        {
          equalledHighestValue = true;
        }

        if ( biLoopHighest.compareTo( biGeneralHighestValue ) > 0 )
        {
          improvedHighestValue = true;
          biGeneralHighestValue = biLoopHighest;
        }

        if ( stepCount > generalHighestStepCount )
        {
          generalHighestStepCount = stepCount;
          improvedHighestStepCount = true;
        }

        if ( equalledHighestStepCount == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " equalled the highest step count at "
             + nf.format( generalHighestStepCount )
             + " -  -  -  -  -  -  -  -"
             + " reaching a peak value of "
             + biFormat( biLoopHighest )
          );
        }

        if ( improvedHighestStepCount == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " improved the highest step count to "
             + nf.format( generalHighestStepCount )
             + " -  -  -  -  -  -  -  -"
             + " reaching a peak value of "
             + biFormat( biLoopHighest )
          );
        }

        if ( equalledHighestValue == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " equalled the highest value seen at "
             + biFormat( biGeneralHighestValue )
             + " -  -  -  -  -  -  -  -"
             + " using "
             + nf.format( stepCount )
             + " steps"
          );
        }

        if ( improvedHighestValue == true )
        {
          System.out.println
          (
             "starting value "
             + nf.format( loopIndex + loopOffset )
             + " improved the highest value seen to "
             + biFormat( biGeneralHighestValue )
             + " -  -  -  -  -  -  -  -"
             + " using "
             + nf.format( stepCount )
             + " steps"
          );
        }

      }
    }
    System.out.println
    (
      "Did "
      + bigintLoops
      + " BigInteger loop calculations."
    );
    System.exit(0);
  }

  private static void usage()
  {
    System.err.println
    (
        "usage:"
      + "\r\n"
      + "  java Hailstone howManySteps "
      + "  [ initialStartingOffset [ highStep highValue]]"
      + "\r\n"
      + "where:"
      + "\r\n"
      + "  howManySteps is how many values to do the calculation for;"
      + "\r\n"
      + "  initialStartingOffset is how many integers, from one, to skip;"
      + "\r\n"
      + "  highStep is the high step count as of the initialStartingOffset;"
      + "\r\n"
      + "  highValue is the (possible comma punctuated BigInteger) highest"
      + "\r\n"
      + "  ascent reached by any hailstone as of the initialStartingOffset."
    );
    System.exit(1);
  }

  private static String biFormat( BigInteger bi )
  {
    StringBuffer sbValue = new StringBuffer( bi.toString() );
    char comma = ',';
    int size = sbValue.length();
    int numCommas = ( size - 1 ) / 3;
    for ( int i = 1; i <= numCommas; i++ )
    {
      sbValue.insert( size - (3 * i), comma );
    }
    return sbValue.toString();
  }

  // Cater for cut and paste of comma-punctuated BigIntegers in args[].

  private static BigInteger biParse( String bis )
  {
    StringBuffer bisb = new StringBuffer( bis );
    while ( bisb.indexOf( "," ) != -1 )
    {
      bisb.deleteCharAt( bisb.indexOf( "," ) );
    }

    return new BigInteger( bisb.toString() );
  }

}