Collatz Conjecture

Ah, nothing like the classics! For the ininitiated, the Collatz conjecture says this:

Start with any positive integer n. Then each term is obtained from the previous term as follows:

• If the previous term is even, the next term is one half the previous term.
• If the previous term is odd, the next term is 3 times the previous term plus 1.

The conjecture is that no matter what value of n, the sequence will always reach 1.

Now, if you read my last two posts, you may be of the impression that I throw recursion at everything. This post probably doesn't help that impression, so you'll have to take me at my word when I tell you that I have an equal appreciation for iteration. And where Collatz is concerned, recursion is terrible when n gets large and that vector blows up. That said, this is my recursive implementation that proves Collatz in C++.

auto collatz(const int n) -> std::vector<int>
{
  /* Validate input */
  if(n <= 1)
    return std::vector<int>();
  std::vector<int> out{n};
  return collatz(out);
}

auto collatz(std::vector<int>& out) -> std::vector<int>
{
  auto const this_n {out.back()};
  if(this_n == 1)
    return out;
  else if(this_n%2)
    out.push_back((this_n * 3) + 1);
  else
    out.push_back(this_n/2);
  return collatz(out);
}

I have the function overloaded to make it callable with just an integer (this is how the user would use it), but also with a vector if ints so it can fill the vector one entry at a time, one function call at a time.

main() looks like this:

auto main(int argc, char** argv) -> int
{
  int original_n{atoi(argv[1])};

  std::vector<int> result {collatz(original_n)};

  std::cout << "Result: [ ";
  for(const auto& it : result)
    std::cout << it << " ";
  std::cout << "]" << std::endl;

  return EXIT_SUCCESS;
}

When called with ./collatz.o 25, the output is as follows:

Result: [ 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 ]

Pretty nice, huh? I remember doing this for the first time in MATLAB back in college, and I think it might have been the first time I actually attempted to apply programming to a problem that I was actually curious about. Nowadays, I get to do that for a living, which is something that I'm very grateful for.

Cheers!