Project Euler: Problem 14

The following iterative sequence is defined for the set of positive integers:

n \to n/2 (n is even)
n \to 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1

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;
}

var answer = startOfLongest;

I don’t know if there really is much to say about that code. It is pretty straight forward. For each number, do the chain stuff until you reach 1. If the chain was longer than what we have found so far, store it. Then move on to the next one.

It runs in around 480 milliseconds so not among the fastest solutions I have had so far, but fast enough. I tried to come up with a more fancy solution, but they just took longer or didn’t work at all, so I’ll spare you the details of those :P

How did you do? Do you see any obvious inefficient parts in my code? Can it be optimized somehow? Please let me know in the comments below :)

  • http://www.facebook.com/peter.mitrano Peter Mitrano

    hey so I copied this directly, and ran it. It doesn’t work.
    I did this because I wrote an almost identical program, and had no idea why it wasn’t working. it works under 134379 but for some reason that number doesn’t come down to one. It just keeps getting bigger and bigger. HELP?

    • nick

      dude I have the same exact problem. It’s really frustrating, because everyone has code with the exact logic I used and theirs work.