Collatz graphs and Perl 6

I wanted to play around a bit with numbers in Perl 6, so the Collatz Conjecture seemed like a good place to start.

The Collatz Conjecture is a simple statement which has some massive implications:

f(n) = if n is even n/2, otherwise (n x 3)+1

Given that n is a positive integer, repeated applications will eventually yield 1.

So, for example, n=10. On the first step, we get 5 because 10 is even, so we divide by two. On the second step, we get 16 because 5 is odd, so we multiply by 3 and add 1. Because 16 is a power of 2, we know that continuing to divide it by 2 will eventually give us 1, and all results until we reach 1 will be even so we're done. In fact, so far every number tested works this way but no one can, as yet, mathematically prove that there isn't an exception.

My code is fairly simple. It works backwards from 1. You can only get to 1 from 2 because there's no odd, positive integer (0 doesn't count, here) that when multiplied by 3 and incremented by 1, is 1. So then we work on 2, which can only be arrived at from 4. 4 can be arrived at from 1, but 1 is the end of the process, so we ignore that. It can also be arrived at from 8. 8 Can be arrived at from 16, but as we know from above 16 can be arrived at from 5 as well as 32, so that's our first branch in the tree. This process can be repeated for as long as you have enough computer memory to store all of the current branch-points.

That's exactly what I do, and I configured it so that you simply input a depth of tree you want to output and it outputs every value in a tree of that depth.

If you would like to see the code, check it out on github. The output svg file is also in the same directory for the tree-like output and the radial output from the twopi filter, along with the Graphviz source. I generated the following graph with the help of my good friends Graphviz and rsvg. The whole depth-20 graph looks like this:

But, of course, it's hard to make anything out there, so here's a close-up:

There are some interesting things that jump out at me in this. Because you can only ever get to a multiple of 3 from its double (since n-1 is never divisible by 3 if n is), once you hit any number that's divisible by 3, you embark on a straight line, like the one you see above at 213. The other thing that becomes obvious is that even fairly low numbers (like 19) don't appear until very late in the process. That there's no duplication in this graph is really fascinating.

The most interesting part of the Collatz Conjecture, I think, is that it can be expressed so easily that anyone with a rudimentary amount of math skills can understand it. This makes it accessible to a wider audience than any other unsolved problem in math that I can think of, and yet it's never been solved. Interesting stuff.

Anyway, enjoy your own explorations of the Collatz Conjecture and don't get too engrossed, or you might find that you're a bit too much like this XKCD comic: http://xkcd.com/710/