Project Euler – Problem 14 Longest Collatz sequence, or “What I didn’t learn from problem 8”

As my regular reader will doubtless remember, I recently blogged about the important lesson I learnt while solving problem 8. I prophetically commented there…

“So, am I going to contemplate my problem domain before diving in and coding next time? Probably not, but at least if I don’t, I might have some idea where to look when the bug reports come in!”

Hmm, I thought I was joking! Well, sadly I wasn’t.

Faced with problem 14, I jumped right in and began coding as usual. My first attempt looked like this…

let collatz n =
  Seq.unfold (fun i -> if i % 2 = 0 then Some(i, i / 2) else Some(i, 3 * i + 1)) n
let collatzLength n =
  (collatz n |> Seq.takeWhile (fun n -> n <> 1) |> Seq.length) + 1

I had tested this on a smaller range, and it worked fine. Remembering what I thought I had learnt from problem 8, I did a quick scan of the range of numbers generated, and satisfied that an int would cope with it, set off to solve the problem…

[1..1000000] |> Seq.map (fun n -> n, collatzLength n) |> Seq.maxBy snd

Whereas this had only taken a second or two on small ranges, it churned away for a very long time when given the full range, ie up to one million. Although a million is quite a lot, it shouldn’t have taken that long to solve.

I tried the problem in C#, and had the same issue…

  int maxColl = 0;
  int maxLen = 0;
  for (int i = 2; i < 1000000; i++) {
    int coll = i;
    int len = 1;
    while (coll != 1) {
      if (coll % 2 == 0) {
        coll = coll / 2;
      } else {
        coll = 3 * coll + 1;
      }
      len++;
    }
    if (len > maxLen) {
      maxLen = len;
      maxColl = i;
    }
  }

Somewhat frustrated and baffled, I gave up and started searching around for other people’s code. I came across a C# solution that looked remarkably like the one above, that ran in about 2.4s. This was even more frustrating.

Eventually, it was pointed out to me that when you run it with the full range of starting points, some of the intermediate numbers generated in the sequence grow larger than the limits of an int, which causes the number to overflow. Under normal circumstances, this doesn’t cause an exception, but means that the number goes negative. Once that happens, the Collatz sequence will never go positive again, so will never terminate (assuming we consider the value 1 as the end of the sequence). This was easily confirmed by adding a “checked” block around the C# code, and seeing the exception thrown. Changing the “int” to “long” in the code above allowed it to give the correct answer in about 2.3s.

So what should I have learnt?
Well, I should have taken more care over my number ranges, just like in problem 8. The sad thing is that I thought I had, but I obviously didn’t check carefully enough.

Thinking about it, when the code took so long, I should have put some logging in there to show where it was up to. That would have shown the problem immediately, as I would have seen the negative values in the sequence. Strike One.

The other point is that it raises the issue of validating your input. If my function had done this, I would have found the problem very quickly. For example, changing my collatz function as follows would have raised the issue as soon as I tried to run it…

let collatz n =
  Seq.unfold (fun i -> 
    if i <= 0 then failwith "The input must be at least 1"
    if i % 2 = 0 then Some(i, i / 2) else Some(i, 3 * i + 1)) n

This sort of issue comes up more often than you might think. As developers, we (and I use the plural deliberately, I’ve seen plenty of others make the same mistakes) bravely assume that the values sent into our functions/methods are within acceptable ranges. When they aren’t, we get exceptions that are often very hard to debug.

Microsoft began to address this issue with Code Contracts. In theory, these are an excellent and easy way to address exactly this problem. In practice, I never found them to work, and gave up. Maybe it’s time to revisit them and try again.

Another day, another lesson ignored!

Be First to Comment

Please note that all comments are manually approved before being displayed, so don't bother posting spam, I'll just delete it

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.