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
About these ads
Leave a comment

5 Comments

  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?

    Reply
    • 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.

      Reply
  2. brennydoogles

     /  March 10, 2010

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

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

    Reply
  1. Too many languages… | Inside a Calculator

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.