Graphing the Collatz Conjecture

CollatzTree_Banner3

The Collatz Conjecture (also known as hailstone sequences or the 3x+1 problem) is a problem in Mathematics first proposed some 60 years ago. It goes like this: Pick any positive integer. If the number is positive, we halve it. If it is odd we multiply it by 3 and add 1. Keep applying this rule until you reach a repeating sequence of numbers. For example let’s start with either of the numbers 3 or 20 and apply these rules.

CollatzTree_3&20

As long we follow these rules our numbers will go up and down for a while before reaching a repeating sequence (4 -> 2 -> 1 -> 4 -> 2 etc). Once we reach 1 we tend to stop counting. This starts slow but gets a lot cooler after the break.

Starting small

The conjecture states that any positive integer you can think of will converge to this 4-2-1 sequence. This gives way to some fun branching networks which you can see the beginnings of above since both 20 (n/2) and 3 (3n + 1) lead to 10. The networks don’t seem too complicated at first. Every number up to 26 gives the following network.

CollatzTree_26

Some paths spike up and down (by the way this is where the alternate name of ‘hailstones’ comes from) like 15 which reaches 160 before coming back down. So far though every numbers hits the 4-2-1 sequence pretty quickly. This changes when you add the path for 27 and the old network explodes.

CollatzTree_27

Prior to 27, the longest chain was 25 which took 23 steps to reach 1. 27 however takes 111 steps, reaching a maximum value of 9,232 before reaching 1.

This is part of what has made the Collatz conjecture so difficult to prove. There’s no real pattern to how these chains form. People have thrown some pretty impressively crazy computing power at this problem and still haven’t been able to prove the conjecture. To the best of anyone’s knowledge, if there is a number that doesn’t approach the 4-2-1 sequence, it will be absolutely colossal. It does produce some pretty cool networks though.

Ramping Up

But enough with the mathematics. The real fun of Collatz is mapping it. By increasing the number of nodes and increasing the twisting effect, things begin to get pretty awesome.

Collatz Sequence for Numbers 1 through 500
CollatzTree_500
Collatz Sequence for Numbers 1 through 5,000
CollatzTree_5000
Collatz Sequence for Numbers 1 through 50,000
CollatzTree_50000
Collatz Sequence for Numbers 1 through 100,000
CollatzTree_100000

At this point technology began to fail me and producing anything larger was difficult/impossible. Chrome couldn’t plot or calculate 200,000 nodes, my JSON files were 2GB large, Inkscape couldn’t import it, etc.

A word on technology

The graphs are created using d3. This is the first time I’ve ever used d3. Although it seems extremely powerful, it isn’t exactly intuitive to use (for me anyway). I spent a lot of time looking for tutorials, butchering sample code and just generally modifying code I couldn’t understand to see what happened. To tell the truth I’m still not entirely sure how the graphs I produced actually work. I found in order to get the twisting effect shown in the later images I had to modify values in the actual d3.v3.js file itself.

In the end I had to give up on some bells and whistles I was hoping I could implement just because I couldn’t work out parts of d3. I’m hoping if I keep using d3 for other things I might start to pick a few things up and I’ll be able to make another pass at this a few months from now.

In the examples above I was feeding JSON files into d3 as an input. I wrote a python script to create JSON files of hailstone sequences up to value N. This was also my first attempt using Python and sweet baby jesus it is an easy language to use. I wish I’d learnt to use this earlier.

Next Steps and Other Thoughts

To be honest I’ve been working on for this for a pretty long time, so not really filled with a burning desire to keep working on Collatz stuff right now. However there are some things I didn’t get around to that I might have a crack at later

  • Prettyifying the graphs so they produce something worthy of a desktop wallpaper.
  • Hosting the d3 code on an interactive webpage where you can use a slider to choose how high to plot.
  • Playing around with other versions of Collatz. eg: Try plotting it in something other than base 10, or see what happens when you allow negative numbers or fractions.

Further Reading on the Collatz Conjecture

Leave a Reply