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

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
                start = start * 3 + 1
    yield 1

if __name__ == "__main__":
    for i in collatz(10):
        print i
Leave a comment


  1. 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. 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

  1. Too many languages… | Inside a Calculator

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: