Collatz Conjecture in Python

The Collatz's Conjecture states that any number can either be halved (if it is even) or multiplied by three and added one to (if it is odd) and eventually reach 1.

I was wondering if there was a more efficient way to work out the series that a number takes to get to one and the amount of steps it takes. The Python (3.x) code is:

i, k = 1, 1
fh=open("results.txt", "w")
print("Started")
def colapatz(x):
    seq = [x]
    j = 0
    while x > 1:
       if x % 2 == 0:
         x = x / 2
         j = j + 1
       else:
         x = 3 * x + 1
         j = j + 1
       seq.append(x)
    fh.write("Value number " + str(i) + " takes "+ str(j) + " steps.\n")
    fh.write("It takes the sequence: " + str(seq) + "\n")

#Call the function
while k<10000:
    k+=1
    i+=1
    colapatz(i)
print("Finished")
fh.close()

The is one of my first python programs that I've ever written, so any improvements would be great.

One possible improvement is to use recursion and memoization to implement a "dynamic programming" solution. This uses the results of previous calculations to speed up the process, as you will end up calculating the same sub-sequences repeatedly. For example:

def memo(f):
    def func(*args):
        if args not in func.cache: 
            func.cache[args] = f(*args)
        return func.cache[args]
    func.cache = {}
    return func

@memo
def collatz(n):
    if n == 1:
        count, seq = 0, []
    elif n % 2:
        count, seq = collatz(3 * n + 1)
    else:
        count, seq = collatz(n // 2)
    return count + 1, [n] + seq

(Note the use of a decorator to implement the memoization.)

Now, once you've run:

>>> collatz(10)
7, [10, 5, 16, 8, 4, 2, 1]

then e.g. collatz(8) can just be looked up from the cache, so future calculations aren't needed:

>>> collatz.cache
{(1,): (1, [1]), (2,): (2, [2, 1]), (8,): (4, [8, 4, 2, 1]), 
 (4,): (3, [4, 2, 1]), (10,): (7, [10, 5, 16, 8, 4, 2, 1]), 
 (5,): (6, [5, 16, 8, 4, 2, 1]), (16,): (5, [16, 8, 4, 2, 1])}

The downsides of this are:

• It uses up a lot of space; and

• As it's recursive, a long sequence can hit the recursion limit and crash the program.

Also, note that count == len(seq), so you don't necessarily have to return (and store) both.

StackExchange Code Review Q#66830, answer score: 7