Introduction
One evening, you stumbled upon an old notebook filled with cryptic scribbles, as though someone had been obsessively chasing an idea.
On one page, a single question stood out: Can every number find its way to 1?
It was tied to something called the Collatz Conjecture, a puzzle that has baffled thinkers for decades.
The rules were deceptively simple.
Pick any positive integer.
- If it’s even, divide it by 2.
- If it’s odd, multiply it by 3 and add 1.
Then, repeat these steps with the result, continuing indefinitely.
Curious, you picked number 12 to test and began the journey:
12 ➜ 6 ➜ 3 ➜ 10 ➜ 5 ➜ 16 ➜ 8 ➜ 4 ➜ 2 ➜ 1
Counting from the second number (6), it took 9 steps to reach 1, and each time the rules repeated, the number kept changing.
At first, the sequence seemed unpredictable — jumping up, down, and all over.
Yet, the conjecture claims that no matter the starting number, we’ll always end at 1.
It was fascinating, but also puzzling.
Why does this always seem to work?
Could there be a number where the process breaks down, looping forever or escaping into infinity?
The notebook suggested solving this could reveal something profound — and with it, fame, fortune, and a place in history awaits whoever could unlock its secrets.
Instructions
Instructions
Given a positive integer, return the number of steps it takes to reach 1 according to the rules of the Collatz Conjecture.
Dig Deeper
If/Else
If / Else
def steps(number):
if number <= 0:
raise ValueError("Only positive integers are allowed")
counter = 0
while number != 1:
if number % 2 == 0:
number /= 2
else:
number = number * 3 + 1
counter += 1
return counter
This approach starts with checking if the number is less than or equal to zero.
If it is, then it raises a ValueError.
After that, we declare a counter variable and set it to zero.
Then we start a while loop that will run until the number is equal to one.
Meaning the loop won’t run if the number is already one.
Inside the loop we check if the number is even.
If it is, then we divide it by two.
If it isn’t, then we multiply it by three and add one.
After that, we increment the counter by one.
After the loop completes, we return the counter variable.
We use a while loop here because we don’t know exactly how many times the loop will run.
Ternary operator
Ternary operator
def steps(number):
if number <= 0:
raise ValueError("Only positive integers are allowed")
counter = 0
while number != 1:
number = number / 2 if number % 2 == 0 else number * 3 + 1
counter += 1
return counter
This approach starts with checking if the number is less than or equal to zero.
If it is, then a ValueError is raised.
After that, a counter variable is assigned to zero.
Then we start a while loop that will run until the number is equal to one.
Meaning the loop won’t run if the number is already one.
Inside the loop we have a ternary operator or [conditional expression][conditional-expression].
A ternary operator/conditional expression can be viewed as a one-line if/else statement.
Using a one-line construct can make the code more concise.
We assign the number value to the result of the ternary operator.
The ternary operator/conditional expression checks if the number is even.
If it is, then we divide it by two.
If the number is not even, we multiply by three and add one.
Then the counter is incremented by one.
When the loop completes, we return the counter value.
Recursion
Recursion
def steps(number):
if number <= 0:
raise ValueError("Only positive integers are allowed")
if number == 1:
return 0
number = number / 2 if number % 2 == 0 else number * 3 + 1
return 1 + steps(number)
This approach uses concept:python/recursion to solve the problem.
Recursion is a programming technique where a function calls itself.
It is a powerful technique, but can be more tricky to implement than a while loop.
Recursion isn’t that common in Python, it is more common in functional programming languages, like: Elixir, Haskell, and Clojure.
This approach starts with checking if the number is less than or equal to zero.
If it is, then it raises a ValueError.
After that, we check if the number is equal to one.
If it is, then we return zero.
We then use the same conditional expression/ternary operator as the ternary operator approach does.
We assign number to the result of the conditional expression.
The expression checks if the number is even.
If the number is even, we divide it by two.
If it isn’t, we multiply it by three and add one.
After that, we return one plus the result of calling the steps function with the new number value.
This is the recursion part.
Solving this exercise with recursion removes the need for a “counter” variable and the instantiation of a loop.
If the number is not equal to one, we call 1 + steps(number).
Then the steps function can execute the same code again with new values.
Meaning we can get a long chain or stack of 1 + steps(number) until the number reaches one and the code adds 0.
That translates to something like this: 1 + 1 + 1 + 1 + 0.
Python doesn’t have tail call optimization.
Which means that the stack of 1 + steps(number) will grow until it reaches the recursion limit.
In Python, we can't have a function call itself more than 1000 times by default.
Code that exceeds this recursion limit will throw a [RecursionError](https://docs.python.org/3/library/exceptions.html#RecursionError).
While it is possible to adjust the [recursion limit](https://docs.python.org/3/library/sys.html#sys.setrecursionlimit), doing so risks crashing Python and may also crash your system.
Casually raising the recursion limit is not recommended.
Source: Exercism python/collatz-conjecture