collatz.rb

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

# Given a number n in the Collatz sequence,
# if n is even, the next number in the sequence is n/2
# if n is odd, the next number in the sequence is 3n + 1

# Applying the rule above with the starting number 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?

class Collatz
  attr_reader :longest_num, :longest_length, :lengths

  def initialize(max)
    abort "Invalid maximum number." if max < 1

    @longest_num = 0
    @longest_length = 0
    @lengths = Hash.new
    @max = max
  end

  # By definition, the length of the chain for THIS number is 1 + the
  # length of the chain for the NEXT number. So, we recursively
  # calculate the lengths for each number in the chain, remembering
  # which number had the longest chain, AND the length of the chain,
  # ignoring any numbers over max.

  def length(num)
    puts "caclulating #{num}" if $DEBUG

    # have we already calculated the length for this number?
    if @lengths[num]
      # yes, just return it
      return @lengths[num]
    end

    # is the number 1?
    if num == 1
      # I *believe* this terminates the recursing. I would think that
      # you stop once you reach 1.
      @lengths[num] = 1
    else
      if num % 2 == 0
        # even
        @lengths[num] = length(num/2) + 1
      else
        # odd
        @lengths[num] = length((num*3) + 1) + 1
      end
    end

    # is the number < @max and the longest chain?
    if num <= @max && @lengths[num] > @longest_length
      # yes, so remember it.
      @longest_num = num
      @longest_length = @lengths[num]
    end

    if num <= @max
      # only print the result for numbers < @max
      puts "result #{num} = #{@lengths[num]}" if $DEBUG
    end

    # return the length for this number
    @lengths[num]
  end
end # Collatz

max = (ARGV.shift || '999999').to_i

start_time = Time.now
collatz = Collatz.new(max)

max.downto(2) do |num|
  collatz.length(num)
end

puts "Number with longest chain is #{collatz.longest_num()}"
puts "Length of longest chain is   #{collatz.longest_length()}"
puts "Time taken                   #{Time.now - start_time}"

# dump the results as an array
p collatz.lengths[1,max+1] if $DEBUG