# Collatz Conjecture in Python

After a brief comment thread on a pretty cool blog I decided to post a little bit more about generators. We were discussing the viability of using a generator for finding the sequence of numbers following the Collatz Conjecture for any number. For those unfamiliar with the Collatz Conjecture, it is as follows from Wikipedia:

Consider the following operation on an arbitrary positive integer:
If the number is even, divide it by two.
If the number is odd, triple it and add one.
In modular arithmetic notation, define the function f as follows: Now, form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next. [… It will eventually end in 1 …]

Or more aptly put by xkcd.com: The original code in question was well written, but relied upon recursion to perform it’s function. I proposed that perhaps a generator would be a better way to test the conjecture (which by the way has neither been proven or disproved). Here is the code I came up with for the generator:

```def collatz(start):
while start != 1:
yield start
if start > 1:
if start % 2 == 0:
start = start / 2
else:
start = start * 3 + 1
yield 1

if __name__ == "__main__":
for i in collatz(10):
print i
```

1. #### Mike Moran

/  March 8, 2010

Just tried out your code, and it is pretty slick. I’m pretty sure I’m understanding generators much better now after reading through your post and the “Dive Into Python” pages on it. Definitely a good skill to learn!

It would be interesting to see over which starting numbers one or the other of our codes grabs the sequence faster. Do you know of any way we could check that?

• #### brennydoogles

/  March 8, 2010

That would be cool. Let me poke around and see what I can find. In order to have an easily measurable benchmarking, we may have to find the longest known Collatz chain and try to emulate it. I will poke around for some benchmarking tools and a nice number for the test.

2. #### brennydoogles

/  March 10, 2010

Tests are being run now, I hope to post some results later tonight.

3. #### Mensanator

/  March 24, 2010

Longest known sequence? Sequences are unbounded. It’s trivial to create a sequence in reverse that will run for an infinite (or more practically, arbitrary)
length sequence.

4. #### Andrew

/  May 30, 2017

I’ve rewriten it through lambda
def collatz(start):
while start != 1:
yield start
if start > 1:
start = (lambda y: y * 3 + 1 if y % 2 != 0 else y // 2)(start)
yield 1