Project Euler

For last time's problem I've been wanting to go through it with Jeroen before posting, and he's been away and I've been busy so I haven't had a chance to discuss it yet and write it up. It is coming, promise.

Project Euler contains a large number of mathematical puzzles that can be solved fairly easily (so they say) with not too complex computer programs. I've chosen one of them more or less at random as an introduction. If you're into these problems there are plenty to keep you occupied on Project Euler.

Problem 14

Problem 14 features a couple of simple formulae but quite a lot of counting.

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

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

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

13 40 20 10 5 16 8 4 2 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.

I've not solved this one myself yet, but I think I know what a solution might look like. Given my track record though… I think it might be doable in O(n) if you also use O(n) memory and that ought to run in less than a minute.