Fun with Ruby and the Collatz Conjecture

I’ve been growing a little hungry to dive back into Ruby a bit and the opportunity arose after stumbling on reading about the Collatz Conjecture (of which there is a funny xkcd comic) and finding some spare time on a connecting flight. It basically states that for any number, if you continually divide by two, if even, or multiply by three and add 1, if odd, you will eventually get to 1. All of the intermediate numbers are referred to as the path that make up that number; for example, the number 5 has the following path: [16, 8, 4, 2, 1] where the steps are 5 (x 3 + 1) => 16 (/ 2) => 8 (/ 2) => 4 (/ 2) => 2 (/ 2) => 1. I thought I would have a bit of fun with this and build some utility functions around what you might want to know about two number paths in the collatz conjecture. All of this code was written very hastily but it was fun and killed a couple of hours of boredom stuck on a plane. This is the result:

#!/usr/bin/env ruby

class Collatz
  def self.get_convergence_point(number_one, number_two)
    self.get_path_intersection(number_one, number_two).first
  end

  def self.get_path_intersection(number_one, number_two)
    # Get the paths
    path_one = self.get_path(number_one)
    path_two = self.get_path(number_two)

    # Return the intersection
    path_one & path_two
  end 

  def self.get_path_matrix(number, matrix=Hash.new)
    # Get all of the "child" numbers for this number
    numbers = self.get_path(number)

    # Itterate
    numbers.each do |n|
      # Save some work
      if (matrix[n].nil?)
        matrix[n] = self.get_path(n)

        # Done
        if (n == 1)
          return matrix
        end

        # Recursive
        return self.get_path_matrix(n, matrix)
      end
    end
  end

  def self.get_step_count(number)
    self.get_path(number).length - 1
  end

  def self.get_path(n, numbers=Array.new)
    # Append current itteration
    numbers << n

    # Done
    if (n == 1)
      return numbers
    end

    # Recursive
    if(n%2 == 1)
      self.get_path((3*n)+1, numbers)
    else
      self.get_path(n/2, numbers)
    end
  end
end

## Get some info
matrix_one = Collatz::get_path_matrix(ARGV[0].to_i)
matrix_one_step_count = Collatz::get_step_count(ARGV[0].to_i)
matrix_two = Collatz::get_path_matrix(ARGV[1].to_i)
matrix_path_intersection = Collatz::get_path_intersection(ARGV[0].to_i, ARGV[1].to_i)
matrix_convergence_point = Collatz::get_convergence_point(ARGV[0].to_i, ARGV[1].to_i)

puts matrix_one.inspect
puts matrix_one_step_count.inspect
puts matrix_two.inspect
puts matrix_path_intersection.inspect
puts matrix_convergence_point

## Empty space
puts
puts

## Print "pretty" path
path_one = Collatz::get_path(ARGV[0].to_i)
path_two = Collatz::get_path(ARGV[1].to_i)
path_convergence_point = Collatz::get_convergence_point(ARGV[0].to_i, ARGV[1].to_i)
path_intersection = Collatz::get_path_intersection(ARGV[0].to_i, ARGV[1].to_i)

if path_one.length >= path_two.length
  left_path = path_one
  right_path = path_two
else
  left_path = path_two
  right_path = path_one
end

left_path -= matrix_path_intersection
right_path -= matrix_path_intersection
path_intersection.reverse.each do |n|
  if (!right_path.empty?)
    puts '  ' + n.to_s
  else
    puts n.to_s
  end
end

if (!right_path.empty?)
  puts ' / \\'
end

left_path.reverse.each do |x|
  next if (x == path_convergence_point)
  puts x.to_s + "   " + right_path.pop.to_s
end

This yields the output:

$ ruby collatz.rb 7 6
{16=>[16, 8, 4, 2, 1], 5=>[5, 16, 8, 4, 2, 1], 11=>[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 22=>[22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 17=>[17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 1=>[1], 34=>[34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 40=>[40, 20, 10, 5, 16, 8, 4, 2, 1], 7=>[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 2=>[2, 1], 13=>[13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 8=>[8, 4, 2, 1], 52=>[52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 20=>[20, 10, 5, 16, 8, 4, 2, 1], 4=>[4, 2, 1], 26=>[26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 10=>[10, 5, 16, 8, 4, 2, 1]}
16
{16=>[16, 8, 4, 2, 1], 5=>[5, 16, 8, 4, 2, 1], 6=>[6, 3, 10, 5, 16, 8, 4, 2, 1], 1=>[1], 2=>[2, 1], 8=>[8, 4, 2, 1], 3=>[3, 10, 5, 16, 8, 4, 2, 1], 4=>[4, 2, 1], 10=>[10, 5, 16, 8, 4, 2, 1]}
[10, 5, 16, 8, 4, 2, 1]
10

  1
  2
  4
  8
  16
  5
  10
 / \
20   3
40   6
13
26
52
17
34
11
22
7