Project Euler Question 14 (Collatz Problem)

Solution 1:

The reason you're stalling is because you pass through a number greater than 2^31-1 (aka INT_MAX); try using unsigned long long instead of int.

I recently blogged about this; note that in C the naive iterative method is more than fast enough. For dynamic languages you may need to optimize by memoizing in order to obey the one minute rule (but this is not the case here).

Oops I did it again (this time examining further possible optimizations using C++).

Solution 2:

Notice that your brute force solution often computes the same subproblems over and over again. For example, if you start with 10, you get 5 16 8 4 2 1; but if you start with 20, you get 20 10 5 16 8 4 2 1. If you cache the value at 10 once it's computed, and then won't have to compute it all over again.

(This is known as dynamic programming.)

Solution 3:

I solved the problem some time ago and luckily still have my code. Do not read the code if you don't want a spoiler:

#include <stdio.h>

int lookup[1000000] = { 0 };

unsigned int NextNumber(unsigned int value) {
  if ((value % 2) == 0) value >>= 1;
  else value = (value * 3) + 1;
  return value;
}

int main() {
  int i = 0;
  int chainlength = 0;
  int longest = 0;
  int longestchain = 0;
  unsigned int value = 0;
  for (i = 1; i < 1000000; ++i) {
    chainlength = 0;
    value = i;
    while (value != 1) {
      ++chainlength;
      value = NextNumber(value);
      if (value >= 1000000) continue;
      if (lookup[value] != 0) {
        chainlength += lookup[value];
        break;
      }
    }

    lookup[i] = chainlength;

    if (longestchain < chainlength) {
      longest = i;
      longestchain = chainlength;
    }
  }
  printf("\n%d: %d\n", longest, longestchain);
}

time ./a.out

[don't be lazy, run it yourself]: [same here]

real    0m0.106s
user    0m0.094s
sys     0m0.012s

Solution 4:

Having just tested it in C#, it appears that 113383 is the first value where the 32-bit int type becomes too small to store every step in the chain.

Try using an unsigned long when handling those big numbers ;)