Let’s kick off this blog with a programming problem. This is number 14 on Project Euler, something I do on and off. The problem deals with the Collatz conjecture, which to my knowledge is still unsolved. It states that given an integer N, let N be the first term in a sequence defined iteratively as:

1. if N is even, the next term is N/2
2. if N is odd, the next term is 3N+1

For example, the sequence starting with 9 is 9-28-14-7-22-11-32-16-8-4-2-1. Which produces a chain of 12 number.The conjecture says that all chains end at 1. The actual problem relating to this post is much simpler: what number produces the longest chain starting with a number less than 1 million?

My solution is straightforward: for the integers 1 through 999999, generate chains as per the definition, and stop when the chain reaches 1. For our purposes, presumably all integers below 1000000 produces a chain that ends at 1. All the while, keep track of the longest chain as well as the number causing the chain along the way.

The solution does rely on one optimization. Suppose we’ve determined the chain length belonging to 21. When performing the iteration on 42, it is not necessary to step through until the chain reaches 1, because the next number in the chain is 21, a number we already have the enumeration for. The problem is made simpler by just wanting the chain length, so we can store the chain length produced by a number in an array, and perform a lookup if the iteration produces a number we know the chain for. My solution steps through the numbers 1 to 999999 in order, so it is possible that N/2 produces a link in the chain we have the length for, and can simply add it.

Here is the code that does it (in C++, which is what I’m most familiar with):

edit: ok don’t know any good methods for embedding code. Until then, here’s a pastebin: http://pastebin.com/WqxhwK8j

The above runs almost instantaneously (supposedly all problems on Project Euler can be solved in 2 minutes), and gives the solution 837799.

My background isn’t in programming, so I’m not a stellar programmer by any standards. I welcome any and all critique, especially on future problems I tackle. Enjoy!

Ben