Skip to content

Instantly share code, notes, and snippets.

@keelerm84
Created May 18, 2013 00:58
Show Gist options
  • Save keelerm84/5602815 to your computer and use it in GitHub Desktop.
Save keelerm84/5602815 to your computer and use it in GitHub Desktop.
3n + 1 Recursive Solution in Ruby
#!/usr/bin/env ruby
# Consider the following algorithm to generate a sequence of numbers. Start
# with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and
# add 1. Repeat this process with the new value of n, terminating when n = 1.
# For example, the following sequence of numbers will be generated for n = 22:
#
# 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
#
# It is conjectured (but not yet proven) that this algorithm will terminate at
# n = 1 for every integer n. Still, the conjecture holds for all integers up to
# at least 1,000,000.
#
# For an input n, the cycle-length of n is the number of numbers generated up
# to and including the 1. In the example above, the cycle length of 22 is 16.
# Given any two numbers i and j, you are to determine the maximum cycle length
# over all numbers between i and j, including both endpoints.
#
# Assume your program will be called like ./code-challenge i j
#
# The output should be i j max-cycle-length
#
# For example,
#
# ./code-challenge 1 10
# 1 10 20
#
# Sample Inputs and Outputs
# 1 10 => 1 10 20
# 100 200 .=> 100 200 125
# 201 210 => 201 210 89
# 900 1000 => 900 1000 174
class Algorithm
@@cache = Hash.new
def process(starting, ending)
max = 0
(starting..ending).each do |number|
result = process_number(number)
max = result if result > max
end
max
end
protected
def process_number(number)
return 1 if number == 1
return @@cache[number] if @@cache.has_key?(number)
@@cache[number] = 1 + process_number(number % 2 == 0 ? number / 2 : 3 * number + 1)
end
end
algorithm = Algorithm.new
printf "%s %s %d\n", ARGV[0], ARGV[1], algorithm.process(ARGV[0].to_i, ARGV[1].to_i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment