# Project Euler: Problem 14

The following iterative sequence is defined for the set of positive integers: (n is even) (n is odd)

Using the rule above and starting with 13, we generate the following sequence: It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

## Solution

This problem has to do with the Collatz conjecture. In short, from Wikipedia:

The Collatz conjecture is an unsolved conjecture in mathematics. It is named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, as the Ulam conjecture (after Stanislaw Ulam), or as the Kakutani’s Problem, or as the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers, or as wondrous numbers.

We take any whole number n greater than 0. If n is even, we halve it (n/2), else we do “triple plus one” and get 3n+1. The conjecture is that for all numbers this process converges to 1. Hence it has been called “Half Or Triple Plus One”, sometimes called HOTPO.

Paul Erdős said about the Collatz conjecture: “Mathematics is not yet ready for such confusing, troubling, and hard problems.” He offered \$500 for its solution. (Lagarias 1985)

Interesting stuff. Ok, maybe not that interesting, but it is at least a problem that we can solve (not the Collatz Problem, but the Euler problem 😉 ). And solving it is pretty simple. Just go through all the numbers below one million, and follow the mentioned algorithm for each number and see which one results in the longest chain.

var startOfLongest = 0U;
var longestChain = 0U;

for (var start = 1000000U; start > 0; start--)
{
var s = start;
var length = 1U;

while (s != 1)
{
if (s % 2 == 0)
s /= 2;
else
s = 3 * s + 1;
length++;
}

if (length < longestChain)
continue;

startOfLongest = start;
longestChain = length;
}