Collatz Sequence in Python. Any improvements?

Question

I am relatively new in programming in Python and this is my fist post in Stack Overflow. Can someone tell me if this code is full proof for Collatz Sequence in Python. Thanks

def collatz(number):
    while True:
        if number % 2 == 0:
            number = number // 2
        else:
            number = 3 * number + 1
        print(number)
        if number == 1:
            break
        

while True:
    try:
        number = int(input("Enter a positive non-zero integer: "))
        if number <= 0:
            print("Please enter a positive non-zero integer.")
        else:
            collatz(number)
            break
    except ValueError:
        print("Please enter a valid integer.")

To check I have tried with negative integer, 0 and 1 and string as an input.

Answer 1

The question is indeed what vague. The code can never be a mathematical proof of the presumption from Collatz. But if you mean if this code can be used to test if a certain number holds the presumption of Collatz. Than yes your code is correct to test this.This presumtion is a easy loop and you are doing that right.

In theory you could make it a bit compacter and faster (but note that the code is already fast enough). Other minor improvements are:

def collatz(number):
    while number != 1:
        if number & 1 == 0:
            number >>= 1
        else:
            number = 3 * number + 1
        print(number)

while True:
    try:
        number = int(input("Enter a positive non-zero integer: "))
        if number <= 0:
            print("Please enter a positive non-zero integer.")
        else:
            collatz(number)
            break
    except ValueError:
        print("Please enter a valid integer.")

This uses uses a bitwise operator: & (for checking the even number), removes an if statement and uses bit-shifting operator: >> And with enormous numbers you probably don't want to print the numbers

Answer 2

A few tips.

Firstly, you should realize that you'll never achieve a proof (that all starting numbers eventually reach 1) by trying a lot of starting numbers and showing that each reaches 1. You'll simply achieve a strong expectation that it does indeed hold true for all positive integers.

You may want to return the number of steps taken for an input to reach 1.

Then you can print [collatz(k) for k in range(20)] to check that it's working.

If all good so far, you may want to try timing [collatz(k) for k in range(10_000)], which would let you tweak the algo for speed (if you like).

I'd write the core code more like:

def collatz(k:Int):
    assert k > 0
    counter = 0
    while k != 1:
        k = k // 2 if k % 2 == 0 else 3 * k + 1
        counter += 1
    return counter

Finally you might be interested to use something like numba to achive a massive (>>100x) speedup. One thing you'll learn from this is that Python is not geared towards tight low-level looping. A lot is happening behind the scenes when you u += 1. If you write the same code in C, you'll notice an extreme performance difference. A tech such as numba can achieve close-to-C speeds.

Answer 3

Instead of while True, could use a condition that CAN exit when/if the conjecture is wrong. There are two ways the conjecture could be proven wrong: 1) the sequence loops to a previously seen number 2) it progressively expands to infinity without converging back to 1.

There is not much you can do for the second one (unless you can prove that a maximum number of iterations of maximum step value can be computed beforehand). for the first one, you can store numbers in a set as you go and check new values against the set.

def collatz(number):
    seen = set()
    while number != 1 and number not in seen:
        seen.add(number)
        if number % 2:
            number = 3 * number + 1
        else:
            number //= 2            
        # print(number)
    return number == 1    # true if 1 reach, False otherwise