Collatz Graph: All Numbers Lead to One

Here is a graph showing the orbits of all numbers under the Collatz map with an orbit length of 19 or less, excluding the 1-2-4 loop.

Orbit length: 1

Background

The Collatz conjecture is as follows.

1. Take any natural number, n.
2. If n is even, divide it by 2.
3. Otherwise, n is odd. Multiply it by 3 and add 1
4. Repeat indefinitely.

The conjecture is that you will always reach 1, no matter what number you start with. At this point, of course, you end up in an endless loop going from 1 to 4, to 2 and back to 1.

Reverse Collatz

Alternatively, we can formulate the conjecture such that 1 leads to all natural numbers, using an inverse relation (see the link for full details).

If we exclude the 1-2-4 loop, the inverse relation should result in a tree, if the conjecture is true.

Credits

Collatz graph generation based on Python code by @TerrorBite. Radial node-link tree layout based on an example in Mike Bostock’s amazing D3 library.

Further Reading

• Collatz conjecture (in reverse) on Wikipedia.
• xkcd #710.
• Hacker News discussion.
• Le problème 3n+1: élémentaire mais redoutable, cycles de longueur 5 and y a-t-il des cycles non triviaux? by Shalom Eliahou.

© Jason Davies 2012.