Tracks
/
Rust
Rust
/
Exercises
/
Collatz Conjecture
Collatz Conjecture

Collatz Conjecture

Easy

Instructions

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.

But sometimes the number grow significantly before it reaches 1. This can lead to an integer overflow and makes the algorithm unsolvable within the range of a number in u64.

Given a number n, return the number of steps required to reach 1.

Examples

Starting with n = 12, the steps would be as follows:

  1. 12
  2. 6
  3. 3
  4. 10
  5. 5
  6. 16
  7. 8
  8. 4
  9. 2
  10. 1

Resulting in 9 steps. So for input n = 12, the return value would be 9.

Last updated 1 February 2023
Edit via GitHub The link opens in a new window or tab
Rust Exercism

Ready to start Collatz Conjecture?

Sign up to Exercism to learn and master Rust with 13 concepts, 103 exercises, and real human mentoring, all for free.