---

From Zero to Hero: Mastering the Collatz Conjecture with Cairo

To solve the Collatz Conjecture in Cairo, create a function that accepts a positive integer. Use a loop that continues until the number is 1, applying the rule (n/2 for even, 3n+1 for odd) in each iteration, while incrementing a step counter to track the process.

Imagine stumbling upon an old, leather-bound notebook in a dusty attic. Its pages are filled with cryptic scribbles, mathematical formulas, and one question that appears over and over: "Can every number find its way back to 1?" This isn't the beginning of a mystery novel; it's the real-life puzzle of the Collatz Conjecture, a problem so deceptively simple that a child can understand it, yet so profoundly complex that it has stumped the world's greatest mathematicians for decades. You feel that familiar spark of curiosity, the programmer's itch to model and solve a puzzle.

You're not just armed with curiosity, though. You have a powerful, modern tool at your disposal: the Cairo programming language. This guide will take you on a journey to tame this mathematical beast. We won't just write code; we will dissect the logic, understand its implementation in a provable computation environment, and transform a fascinating mathematical theory into robust, efficient Cairo code. Prepare to turn that cryptic question into a clear, functional solution.

---

What is the Collatz Conjecture? The Deceptively Simple Puzzle

The Collatz Conjecture, also known as the 3n + 1 problem, the Ulam conjecture, or the Syracuse problem, is a famous unsolved problem in mathematics. Proposed by Lothar Collatz in 1937, it posits that a specific sequence of operations will always lead any positive integer back to the number 1.

The rules of the game are incredibly straightforward:

• Start: Pick any positive integer, let's call it n.
• The Rule:
  • If n is even, the next number in the sequence is n / 2.
  • If n is odd, the next number in the sequence is 3 * n + 1.
• Repeat: Apply this rule to the new number, and continue the process.

The conjecture is that no matter what positive integer you start with, this sequence will eventually reach 1. Once it reaches 1, it enters a simple loop: 1 → 4 → 2 → 1 → ...

A Concrete Example: The Journey of Number 7

To truly grasp its nature, let's trace the path of the number 7:

1. 7 is odd → 3 * 7 + 1 = 22
2. 22 is even → 22 / 2 = 11
3. 11 is odd → 3 * 11 + 1 = 34
4. 34 is even → 34 / 2 = 17
5. 17 is odd → 3 * 17 + 1 = 52
6. 52 is even → 52 / 2 = 26
7. 26 is even → 26 / 2 = 13
8. 13 is odd → 3 * 13 + 1 = 40
9. 40 is even → 40 / 2 = 20
10. 20 is even → 20 / 2 = 10
11. 10 is even → 10 / 2 = 5
12. 5 is odd → 3 * 5 + 1 = 16
13. 16 is even → 16 / 2 = 8
14. 8 is even → 8 / 2 = 4
15. 4 is even → 4 / 2 = 2
16. 2 is even → 2 / 2 = 1

It took 16 steps for the number 7 to reach 1. The sequence seems chaotic and unpredictable, jumping up and down, yet it ultimately finds its way home. Despite extensive computer testing that has verified the conjecture for quintillions of numbers, a formal mathematical proof that it holds true for all positive integers remains elusive.

---

Why Use Cairo to Solve This Algorithm?

Choosing a programming language for an algorithmic problem is about more than just syntax; it's about philosophy, safety, and performance. While you could solve the Collatz Conjecture in almost any language, implementing it in Cairo is a particularly insightful exercise for several reasons.

1. Unmatched Safety and Provability

Cairo is designed for provable computation, which is the backbone of technologies like StarkNet. This means correctness is paramount. Cairo's strong type system, ownership model inspired by Rust, and its use of field elements (felt252) ensure that your code is not just functional but arithmetically sound. For a mathematical problem like this, where integer overflows could theoretically corrupt results for massive numbers, Cairo's robust handling of numbers provides a layer of confidence that is hard to match.

2. Performance and Efficiency

The Cairo Virtual Machine (VM) is designed for high-throughput computation. While the Collatz problem is simple, the principles of writing efficient loops and operations in Cairo are foundational. Understanding how to handle mutable state, perform arithmetic, and control flow efficiently prepares you for building more complex, gas-optimized smart contracts and applications on StarkNet.

3. A Gateway to Web3 and Zero-Knowledge Proofs

Working through classic algorithms like this one is a core part of the kodikra learning path. It serves as a perfect, low-stakes environment to master Cairo's syntax and core concepts. The logic of state transitions in the Collatz sequence (from one number to the next) is a microcosm of state transitions in a decentralized application. Mastering this builds the mental models necessary for advanced blockchain development.

Future-Proofing Your Skills

As of late 2023 and heading into 2024/2025, the demand for developers skilled in ZK-rollups and provable computation is skyrocketing. Learning Cairo isn't just about adding another language to your resume; it's about positioning yourself at the forefront of the next wave of blockchain innovation. Every small problem you solve is a step towards that future.

---

How to Implement the Collatz Conjecture in Cairo: A Deep Dive

Now, let's translate the theory into working Cairo code. Our goal is to create a function that takes a positive integer number and returns the total steps required to reach 1. We will analyze the solution provided in the exclusive kodikra.com module, breaking it down line-by-line.

The Cairo Solution Code

Here is the clean, idiomatic Cairo implementation:

// Function to calculate the number of steps for the Collatz Conjecture.
pub fn steps(mut number: u128) -> Option<u128> {
    if number == 0 {
        return Option::None(()); // The conjecture is defined for positive integers.
    }

    let mut count: u128 = 0;
    
    while number > 1 {
        if number % 2 == 0 {
            // Number is even
            number /= 2;
        } else {
            // Number is odd
            // We need to check for potential overflow before multiplication.
            let max_val: u128 = 0xffffffffffffffffffffffffffffffff; // u128::max()
            if number > (max_val - 1) / 3 {
                return Option::None(()); // Overflow would occur
            }
            number = 3 * number + 1;
        }
        count += 1;
    }
    
    Option::Some(count)
}

Note: The original solution used usize. We've upgraded it to u128 for a larger range and added robust error handling with Option<u128> to make it more production-ready and safe against invalid inputs and overflows, which is a key principle in Cairo development.

Step-by-Step Code Walkthrough

1. Function Signature

pub fn steps(mut number: u128) -> Option<u128> {

• pub fn steps: We declare a public function named steps.
• (mut number: u128): The function accepts one argument, number.
  • The mut keyword signifies that this variable is mutable. We need this because we will be changing its value inside the function as we apply the Collatz rules.
  • We use u128, an unsigned 128-bit integer, to handle a very large range of positive numbers.
• -> Option<u128>: This defines the return type. Instead of just returning a u128, we return an Option<u128>. This is a powerful enum in Cairo (and Rust) that lets us handle cases where a valid result might not be possible. It can be either Some(value) if successful or None if there was an error (like invalid input or an overflow).

2. Input Validation

    if number == 0 {
        return Option::None(()); // The conjecture is defined for positive integers.
    }

The Collatz Conjecture is defined only for positive integers. Our first action is to guard against invalid input. If the input number is 0, we immediately return Option::None, signaling that the operation could not be completed. This is far more graceful than the original assert!, which would cause the program to panic and crash.

3. Initializing the Counter

    let mut count: u128 = 0;

We declare a new mutable variable count and initialize it to 0. This variable will keep track of how many steps we've taken. Its type is also u128 to match the potential number of steps for very large inputs.

4. The Main Loop

    while number > 1 {
        // ... logic inside ...
    }

The core of our algorithm is a while loop. This loop will continue to execute as long as our number is greater than 1. The moment number becomes 1, the condition number > 1 becomes false, and the loop terminates, just as the conjecture's process ends.

5. The Collatz Logic (Even/Odd Check)

        if number % 2 == 0 {
            // Number is even
            number /= 2;
        } else {
            // Number is odd
            // ... overflow check and calculation ...
            number = 3 * number + 1;
        }

Inside the loop, we use an if/else block to implement the two rules:

• if number % 2 == 0: The modulo operator (%) gives the remainder of a division. If number % 2 is 0, the number is even.
• number /= 2;: If even, we perform an in-place division, updating number to its new value.
• else: If the number is not even, it must be odd. We then apply the second rule: number = 3 * number + 1;.

6. Overflow Prevention (Crucial Enhancement)

            let max_val: u128 = 0xffffffffffffffffffffffffffffffff; // u128::max()
            if number > (max_val - 1) / 3 {
                return Option::None(()); // Overflow would occur
            }

This is a critical safety addition. The 3 * n + 1 operation can cause the number to grow very large. If it exceeds the maximum value a u128 can hold, it will overflow, leading to incorrect results. Before performing the multiplication, we check if number is already so large that multiplying it by 3 would exceed the limit. If so, we return Option::None to indicate failure.

7. Incrementing the Step Counter

        count += 1;

After applying either the even or odd rule, one step has been completed. We increment our count variable by one. This line is placed after the if/else block but still inside the while loop, ensuring it runs once per iteration.

8. Returning the Result

    Option::Some(count)

Once the while loop finishes (meaning number has reached 1), the function's job is done. We return the final count, wrapped in Option::Some to match the function's return type, indicating a successful computation.

Visualizing the Logic Flow

Here is an ASCII diagram illustrating the core algorithm's decision-making process.

    ● Start with a number `n`
    │
    ▼
  ┌──────────────────┐
  │ Initialize steps = 0 │
  └─────────┬────────┘
            │
            ▼
    ◆ Is `n` > 1 ? ─────── No ─⟶  Wyndham
   ╱          ╲
 Yes          │
  │           ▼
  ▼        ┌───────────┐
  ◆ Is `n`   │ Return `steps` │
 │   even?    └───────────┘
 │  ╱     ╲
 │ Yes     No
 │  │       │
 ▼  ▼       ▼
┌─────────┐ ┌─────────────────┐
│ n = n / 2 │ │ n = 3 * n + 1   │
└─────────┘ └─────────────────┘
    │           │
    └─────┬─────┘
          │
          ▼
┌────────────────────┐
│ Increment `steps` by 1 │
└──────────┬─────────┘
           │
           └─────────────── Loop Back to `Is n > 1?`

---

Where This Logic Fits: Testing and Project Structure

Writing a function is one thing; ensuring it works correctly within a larger project is another. In the Cairo ecosystem, the primary tool for managing projects and running tests is Scarb.

Setting up a Test Case

To verify our steps function, we should write a unit test. In your Cairo project, you would add a test module, typically annotated with #[cfg(test)].

#[cfg(test)]
mod tests {
    use super::steps; // Import the function from the parent module

    #[test]
    fn test_steps_for_1() {
        assert(steps(1) == Option::Some(0), 'steps for 1 is 0');
    }

    #[test]
    fn test_steps_for_16() {
        assert(steps(16) == Option::Some(4), 'steps for 16 is 4');
    }

    #[test]
    fn test_steps_for_12() {
        assert(steps(12) == Option::Some(9), 'steps for 12 is 9');
    }

    #[test]
    fn test_zero_is_invalid() {
        assert(steps(0) == Option::None(()), 'zero is an error');
    }
}

Running Tests with Scarb

Once your tests are written, you can execute them from your terminal using the Scarb CLI. This command will compile your code and run all functions annotated with #[test].

$ scarb test
Testing project_name ...
Running 4 tests
test project_name::tests::test_steps_for_1 ... ok
test project_name::tests::test_steps_for_12 ... ok
test project_name::tests::test_steps_for_16 ... ok
test project_name::tests::test_zero_is_invalid ... ok
Tests passed.

This testing workflow is fundamental for building reliable Cairo applications, from simple algorithmic modules to complex DeFi protocols.

Analyzing the Iterative Solution

Our implementation uses an iterative approach (a while loop). This is generally preferred for the Collatz problem over a recursive solution, which could easily lead to a stack overflow for numbers that produce very long sequences.

Pros of the Iterative Approach	Cons / Risks
Memory Efficient (No Stack Overflow): It uses a constant amount of memory regardless of the input size, avoiding the risk of stack overflow inherent in deep recursion.	Repetitive Computations: If you were to call steps(10), steps(5), steps(16), etc., within a larger program, you would be re-calculating the path from 16 to 1 every time.
Simple and Readable: The logic is straightforward to follow, mirroring the manual step-by-step process of the conjecture.	Large Number Performance: For astronomically large numbers, the sequence length can be very long, leading to extended computation time. The loop simply runs until it's done.
Easy to Debug: You can easily print the state of number and count in each iteration to trace the execution flow.	Overflow Risk: As we addressed in our enhanced code, the 3n + 1 step can lead to integer overflow if not handled carefully.

Visualizing the Cairo Function's Execution Flow

This diagram shows how our specific Cairo function executes from call to return.

    ● Function `steps(n)` is called
    │
    ▼
  ┌─────────────────┐
  │ Check: Is `n` == 0? │
  └─────────┬─────────┘
            │
   Yes ─────┤
            │
            ▼
    ┌──────────────────┐
    │ Return `Option::None` │
    └──────────────────┘
            │
   No ──────┤
            │
            ▼
  ┌─────────────────────┐
  │ Initialize `count` = 0  │
  └──────────┬──────────┘
             │
             ▼
      ◆ Loop: `n` > 1?
     ╱          ╲
   Yes          No
    │            │
    │            ▼
    │    ┌───────────────────┐
    │    │ Return `Option::Some(count)` │
    │    └───────────────────┘
    ▼
  ┌─────────────────┐
  │ Check: Is `n` even? │
  └─────────┬─────────┘
            │
   Yes ─────┤
            │
            ▼
    ┌───────────┐
    │ `n = n / 2` │
    └───────────┘
            │
   No ──────┤
            │
            ▼
    ┌─────────────────┐
    │ Check for Overflow │
    ├─────────────────┤
    │ `n = 3 * n + 1`   │
    └───────────┬─────┘
                │
    ┌───────────┴───────────┐
    │                       │
    ▼                       ▼
  ┌──────────────────┐
  │ `count += 1`       │
  └─────────┬────────┘
            │
            └──────── Loop Back

---

Frequently Asked Questions (FAQ) about Collatz in Cairo

1. What happens if I input a negative number into the function?

Since our function signature specifies u128 (an unsigned integer), the Cairo compiler will prevent you from even calling the function with a negative literal. If you tried to cast a negative number, it would wrap around to a very large positive number, but direct negative input is a type error, ensuring safety at compile time.

2. Is the Collatz Conjecture proven?

No, it remains one of the most famous unsolved problems in mathematics. While it has been computationally verified for an enormous range of numbers (up to 2^68), no general proof exists that it holds true for all positive integers. It's possible, though considered unlikely, that a number exists which enters a different loop or grows to infinity.

3. Why did we choose Option<u128> as the return type?

Using Option is a best practice in Cairo and Rust for functions that can fail. It forces the caller of the function to handle both the success case (Some(value)) and the failure case (None). This prevents unexpected crashes and makes the program's error-handling logic explicit and robust, which is essential for smart contracts and critical systems.

4. Could this code be optimized with memoization?

Yes, for a scenario where you calculate steps for many numbers, memoization (caching results) would be a powerful optimization. You could use a LegacyMap to store the number of steps for each number you've already computed. When asked to compute for a number `n` again, you'd first check the map. This trades increased memory usage for significantly faster computation time on subsequent calls.

5. What are the performance limitations for extremely large numbers?

The primary limitation is the computation time. Some numbers produce exceptionally long sequences before reaching 1 (this is sometimes called their "hailstone" sequence). While our u128 can handle very large numbers, the `while` loop might run for billions of iterations, taking a considerable amount of time and, in a blockchain context, a large amount of gas.

6. Is a recursive solution possible in Cairo?

Yes, you could write a recursive version. However, it's generally not recommended for this problem. Each recursive call adds a new frame to the call stack. A number with a long Collatz sequence would lead to very deep recursion, quickly causing a stack overflow error and crashing the program. The iterative `while` loop approach is much safer and more memory-efficient.

7. How does this relate to the broader Cairo ecosystem?

This exercise, while academic, builds foundational skills. Understanding integer manipulation, control flow, mutability, and error handling is critical for writing StarkNet smart contracts. The logical rigor required is the same whether you're solving a math puzzle or securing millions of dollars in a DeFi protocol. For more, see the complete Cairo guide on kodikra.com.

---

Conclusion: From Mathematical Mystery to Code Clarity

We've journeyed from the cryptic question in an old notebook to a robust, tested, and safe implementation in Cairo. The Collatz Conjecture serves as a perfect microcosm of the software development process: we start with a seemingly simple problem, uncover hidden complexities (like integer overflows), and use the powerful features of our chosen language to build a reliable solution.

By implementing this algorithm in Cairo, you've done more than just solve a puzzle. You've practiced handling mutable state, writing safe arithmetic operations, and structuring code for testability—all core competencies for a proficient Cairo developer. You've seen how Cairo's design philosophy pushes you towards writing correct and resilient code by default.

This is just one step on your journey. The world of provable computation is vast and full of exciting challenges. Continue to hone your skills, tackle more complex problems, and explore the incredible potential of this technology. To continue your structured learning, be sure to explore our complete Cairo Learning Roadmap and master the next set of challenges.

Disclaimer: The code in this article is based on Cairo syntax and features as of late 2023 (Cairo 2.x). The Cairo language and its ecosystem are under active development, and specific syntax or library features may evolve. Always refer to the official documentation for the latest updates.

---

Published by Kodikra — Your trusted Cairo learning resource.