Collatz conjecture sequence length using a python generator

Question

I am trying to find the length of a Collatz conjecture sequence given by the following algorithm:

The code that I am running with is:

def get_count(n):
    i = 1
    while n != 1:
        (n, i) = (3*n+1 if n%2 else n/2, i + 1)
    return i

Can I implement the same using a python generator? And would using the generator be an improvement for implementing the algorithm, performance wise?

Answer 1

The generator version:

def get_count(n):
    i = 1
    while n != 1:
        (n, i) = (3*n+1 if n%2 else n/2, i + 1)
        yield (n, i)

# usage:  
g = get_count(3)
for x in g:
    print x

OUTPUT:

(10, 2)
(5, 3)
(16, 4)
(8, 5)
(4, 6)
(2, 7)
(1, 8)

Using a generator in this case will not improve anything since the final result is stored in i only when you reach n == 1 (the last iteration).

Using generators has a meaning when each iteration provides a substantial result which can be used in later calls ("kind of" like dynamic programming). So, for example, if you want to calculate factorial(n) but you also want to know the results of factorial(k) for every k < n - then it makes sense to use a generator.

Answer 2

Can I implement the same using a python generator?

Yes, you could yield each successive value. Then you could apply itertools.takewhile on the generator function. Then you could use this piece of code to find the length of the iterator.

And would using the generator be an improvement for implementing the algorithm, performance wise?

Slower I think because some other code is used to process the generator, creating overhead.

P.S. Instead of incrementing i in a while-loop, use for i initertools.count(1) (itertools.count is the same thing as range except the stop value is infinite).