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


unsigned int collatz(unsigned long n, unsigned int memo[]) {
  // If the number is larger than the memory, just calculate and be happy
  if (n > 1000000) {
    if ((n %2) == 0) {
      return 1 + collatz(n/2, memo);
    } else {
      return 1 + collatz(n * 3 + 1, memo);
    }
  }

  // Handle even numbers
  if((n%2) == 0) {
    if (memo[n] == 0) {
      memo[n] = 1 + collatz(n/2, memo);
      return memo[n];
    } else {
      return memo[n];
    }
  }

  // Handle odd numbers
  if (memo[n] == 0) {
    memo[n] = 1 + collatz(n * 3 + 1, memo);
    return memo[n];
  } else {
    return memo[n];
  }
}



int main(void) {
  clock_t begin = clock();
  unsigned int memo[1000001] = {0, 1};

  unsigned int biggest_seq = 1;
  unsigned int biggest_start = 1;
  unsigned int temp = 0;
  for(unsigned int i =1; i<1000000; i++) {
    temp = collatz(i, memo);
    if(temp>biggest_seq) {
      biggest_start = i;
      biggest_seq = temp;
    }
  }
  clock_t end = clock();
  double tspent = (double)(end - begin) / CLOCKS_PER_SEC;

  printf("%d - %d in %f seconds", biggest_start, biggest_seq, tspent);
  return 0;

}