When doing Project Euler problem #14 I was running into a problem.

1
2
3
4
5
6
7
8
9
10
11
12
13

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 started out by writing a method that took a number and returned the length of its Collatz sequence.

1
2
3
4
5
6
7
8
9
10
11
12

def collatz
  array = []
  array << self
  until array.last == 1 do
    if array.last.odd?
      array << (array.last*3 + 1)
    else
      array << (array.last/2)
    end
  end
  array.count
end

I was pretty sure the logic was correct, but when I ran it on a random number it generated a strange error.

1

private method `collatz' called for 12:Fixnum (NoMethodError)

I tried a bunch of different approaches to solve this, but none of them were working. I eventually realized that my method needed to be part of a class. I made a new class called Collatz and made each number a new instance of that class. After half an hour of nothing but error messages I decided I needed a new approach.

Without an internet connection I couldn’t just google the problem, so I thought a bit more. It dawned on me that numbers are already objects (since everything in Ruby is an object) and that they are already part of the Fixnum class.

I’ve never modified a core Ruby class or ‘reopened’ a class before, but I did vaguely remember learning about this in a lecture a few weeks ago. So I decided to just reopen the Fixnum class and add this new method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Fixnum
  def collatz
    array = []
    array << self
    until array.last == 1 do
      if array.last.odd?
        array << (array.last*3 + 1)
      else
        array << (array.last/2)
      end
    end
    array.count
  end
end

I tired it out on a test number and it worked! Victory! This is pretty basic stuff, but it’s always satisfying to get past a problem you are stuck on it for a while. All that was left was to iterate over the first million numbers and determine which one had the longest Collatz sequence.

1
2
3
4
5

array = []
(1..1000000).each do |number|
  array << number.collatz
end
puts array.index(array.max) + 1

The program I built determined correctly that out of the first million numbers - 837,799 has the longest Collatz sequence. My code could be optimized further - it takes a good minute to run now. That would involved determining which numbers I don’t need to iterate over - for instance it seems that even numbers generally (but not always) have longer sequences as you increase, and that odd numbers generally have longer sequences than even numbers.