Last active
December 17, 2021 09:01
-
-
Save Niall47/55577b777b5360befa2cda04d80f3bf0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
=begin | |
Collatz Conjecture | |
Hint: recursion! | |
The Collatz Conjecture or 3x+1 problem can be summarized as follows: | |
Take any positive integer n. If n is even, divide n by 2 to get n / 2. If n is odd, multiply n by 3 and add 1 to get 3n + 1. Repeat the process indefinitely. The conjecture states that no matter which number you start with, you will always reach 1 eventually. | |
Given a number n, return the number of steps required to reach 1. | |
Example: | |
Starting with n = 12, the steps would be as follows: | |
12 | |
6 | |
3 | |
10 | |
5 | |
16 | |
8 | |
4 | |
2 | |
1 | |
Resulting in 9 steps. So for input n = 12, the return value would be 9. | |
n.even? ? n / 2 : (3*n) + 1 | |
=end | |
module Collatz | |
def self.steps(value) | |
# break out if we've reached 1 | |
return 0 if value == 1 | |
# we return 1 + the result of the next value steps returns (which will be 1 or 0) | |
1 + steps(value.even? ? value / 2 : value * 3 + 1) | |
end | |
end | |
n = ARGV.first.to_i | |
throw "Positive integer please" unless n.positive? | |
puts Collatz.steps(n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment