# include <stdio.h> 
# include <stdlib.h>
# include <time.h>

int main ( );
int *collatz_steps ( int steps_num );

/******************************************************************************/

int main ( ) 

/******************************************************************************/
/*
  Purpose:

    COLLATZ finds the longest Collatz sequence between 1 and N.

  Modified:

    07 March 2017

  Author:

    John Burkardt

  Parameters:

    Local, int STEPS[STEPS_NUM], will contain the length of each Collatz
    sequence from 1 to STEPS_NUM.

    Local, int STEPS_NUM, the highest integer to check.
*/
{
  clock_t clock1;
  clock_t clock2;
  int i;
  int i_max;
  int *steps; 
  int steps_num = 10000000;
  int steps_size;
  double value;

  printf ( "\n" );
  printf ( "COLLATZ:\n" );
  printf ( "  C version\n" );
//
//  Call the function that does the work.
//
  clock1 = clock ( );
  steps = collatz_steps ( steps_num ); 
  clock2 = clock ( );

  value = ( double ) ( clock2 - clock1 ) / ( double ) CLOCKS_PER_SEC;
  printf ( "\n" );
  printf ( "  Computation required %g seconds\n", value );
//
//  Find the maximum sequence length.
//
  i_max = 0;
  for ( i = 0; i < steps_num; i++ ) 
  {
    if ( steps[i_max] < steps[i] )
    {
      i_max = i;
    }
  }
  printf ( "\n" );
  printf ( "  In the range [1,%d], the longest Collatz sequence\n", steps_num );
  printf ( "  occurs for N = %d, of length %d.\n", i_max + 1, steps[i_max] ); 
//
//  Free memory on the host.
//
  free ( steps ); 
//
//  Terminate.
//
  printf ( "\n" );
  printf ( "COLLATZ:\n" );
  printf ( "  Normal end of execution.\n" );

  return 0;
}
/******************************************************************************/

int *collatz_steps ( int steps_num )

/******************************************************************************/
/*
  Purpose:

    COLLATZ_STEPS computes the length of a particular Collatz sequence.

  Parameters:

    Input, int STEPS_NUM, the number of integers to check.

    Output, int COLLATZ_STEPS[], the array of Collatz sequence lengths.
    This function will set the I-th value of this array.
*/
{
  int i;
  int n;
  int s;
  int *steps;

  steps = ( int * ) malloc ( steps_num * sizeof ( int ) );

  for ( i = 0; i < steps_num; i++ )
  {
    n = i + 1;
    s = 0;
  
    while ( 1 < n )
    {
      if ( ( n % 2 ) == 0 )
      {
        n = n / 2;
      }
      else
      {
        n = 3 * n + 1;
      }
      s = s + 1;
    }

    steps[i] = s;
  }

  return steps;
}