Project Euler: Longest Collatz Sequence

Question

The Collatz Sequence is an iterative sequence that is defined for all positive integers as such:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

If 13 were to be entered into this sequence, the result would be as follows:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

And the total number of terms in the chain would be 10. The sequence always ends with 1.

You must create a program that will calculate for a value in the range of 2 <= x < 1000000. This value must give the longest chain of terms when inputted into the Collatz Sequence.

I will now post my solution. Any criticism would be greatly appreciated. Did I use too many if/else statements? Was recursion not the best thing to use? Anything you have to say.

File Main.cpp

#include "Main.h"
#include <iostream>

  namespace coll {
    int counter(1);

    long long doEven(long long numb) {
      if (numb != 1) {
        if (numb % 2 == 0) {
          counter++;
          return doEven(numb / 2);
        } else
          return doOdd(numb);
      } else
        return counter;
    }

    long long doOdd(long long numb) {
      if (numb != 1) {
        if (numb % 2 != 0) {
          counter++;
          return doOdd((3 * numb) + 1);
        } else
          return doEven(numb);
      } else
        return counter;
    }

    int chainLength(0);
    int temp(0);
    int theBestInput(0);

    int longestChain(int input) {
      if (input < 1000000) {
        if (input % 2 == 0)
          temp = doEven(input);
        else
          temp = doOdd(input);
        counter = 1;
        if (temp > chainLength) {
          chainLength = temp;
          theBestInput = input;
          input++;
          return longestChain(input);
        } else {
          input++;
          return longestChain(input);
        }
      } else {
        return theBestInput;
      }
    }

    void printResult() {
      std::cout << "LONGEST SEQUENCE: " << longestChain(2) << std::endl;
    }
  }

File Main.h

#pragma once
namespace coll {
  extern int counter;
  extern int theBestInput;
  extern int chainLength;
  extern int temp;
  long long doEven(long long numb);
  long long doOdd(long long numb);
  int longestChain(int input);
  void printResult();
}

File Test.cpp

#include "Main.h"
int main() {
  coll::printResult();
  return 0;
}

Answer 1

I think that you are writing similar functions to make very similar things. You can take advantage of ternary operator ? and make a simpler function instead:

int Collatz( int &len, int number )
{
    std::cout << number << " - ";
    len++;

    if( number == 1 )
        return 1;

    int NextNumber = number % 2 ? number*3+1 : number/2;

    return Collatz( len, NextNumber );
}


int main()
{
    int len = 0;
    Collatz( len, 13);

    std::cout << "Lenght: " << len << std::endl;

    return 0;
}

The output is:

13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1 - Lenght: 10

Answer 2

There are a couple of optimisations that compilers should make, but they often don't:

• n % 2 is identical to n & 1, but the latter is evaluated significantly faster.
• Likewise, n / 2 is identical to n >> 1, but the latter performs better.

Since your code is going to be executed billions of times, it's worth looking into whether your compiler will handle these expressions differently.

Answer 3

This is Project Euler Problem 14. Your solution appears over-complex to me. I solved it in Java, but even so my solution appears a lot simpler. The basics are the same, but you seem to go round the houses to get there.

For example, you have two different methods to calculate the next number in the Collatz sequence, one for evens and one for odds. My code has a single function to do the calculation and count the length of the chain:

int chainLength(long num) {
    int count = 1;
    while (num > 1) {
        num = (num % 2 == 0) ? num / 2 : 3 * num + 1;
        ++count;
    }
    return count;
}

That is Java, but the C++ will be similar (and I was upstaged by David while I was writing this: great minds think alike.)

Your longestChain() function also appears to have a lot of unnecessary code in it. The central loop of my Java equivalent looks like:

int bestLength = 1;
int bestStart = 1;
for (int i = 2; i < 1_000_000; i++) {
   int current = chainLength(i);
   if (current > bestLength) {
       bestLength = current;
       bestStart = i;
   }
}

Again that is Java, but it looks a lot simpler than your version. It uses the chainLength() function above.

With Project Euler I tend to start with a simple and obvious solution to the problem. If that is too slow, then I try something else, but I like to see of the plain and obvious approach works first. This was one of the problems where plain and obvious worked. This one runs in 550ms for me.