/* terminates.c   hailstorm recursion
 *                start with x = positive integer
 * while x > 1               max times through loop is 4*x + 3
 *   if x odd                max value of x in loop is < 13*x*x
 *     x = 3*x+1             always makes next choice even
 *   else
 *     x = x/2
 *                           bad cases include x = 27
 *                           the key to mathematical proof is no repeated value
 *                           conjecture is: always terminates
 */

/* must use at least 64 bit arithmetic, cc -64 on SGI */
 
#include <stdio.h>

int main()
{
  long int x;
  long int count;
  long int maxx;
  long int new_maxx = 0L;
  long int limit = 10000000L;
  long int x_next;

  /* do sequence for x = 27 with full printout */
  printf("initial x = 27, odd/even and next value printed \n");
  count = 0L;
  maxx = 0;
  x = 27L;

  while( x > 1)
  {
    count++;
    if( x & 1L )
    {
      x = 3 * x + 1;
      printf(" odd  %ld \n", x);
    }
    else
    {
      x = x / 2;
      printf(" even %ld \n", x);
    }
    maxx = x>maxx ? x : maxx;
  }
  printf("x=27 done in %ld steps with max %ld \n", count, maxx);
  new_maxx = maxx+1;

  /* now run x from 1 to argv[1] */
  for( x_next=1L ; x_next <= limit; x_next++) 
  {
    count = 0;
    maxx = 0;
    x = x_next;
    while( x > 1)
    {
      count++;
      if( x & 1L )
      {
        x = 3 * x + 1;

      }
      else
      {
        x = x / 2;
      }
      maxx = x>maxx ? x : maxx;
      if(x <= 0) { printf("x negative at %ld \n", x_next); break; }
    }
    if( (count > 4*x_next+3) || (maxx > 13*x_next*x_next))
    {   
       printf("x=%ld fail in %ld steps with max %ld \n", x_next, count, maxx);
       break; /* probably because 13*x_next*x_next bigger than word size. */
    }
    if( x_next % 100000 == 0 ) printf("passing %ld \n", x_next);
    if( maxx > new_maxx ) 
    {
      new_maxx = maxx;
      printf("x=%ld new max in %ld steps with max %ld \n", x_next, count, maxx);
    }
  }

  return 0;
}