Collatz sequences
The Collatz sequence for a whole number n is generated by iterating:
a_n = (1/2) * a_n-1 if a_n-1 is even
a_n = 3*a_n-1 + 1 if a_n-1 is odd
The Collatz conjecture is that this sequence always terminates at 1. The Wikipedia entry has a graph by Jon McLoone, Director at Wolfram Research and all-around interesting person. I thought that was cool and wanted to make my own, so here’s what I came up with:
Also, check out the humungo version and the source that generated it using pygraphviz and GraphViz.
Why does this work? Thinking in terms of prime factors, the half rule removes factors of 2. The triple-plus-one rule increases the next value, but makes sure there’s always at least one factor of 2 to remove. For the cases where triple-plus-one yields more than one factor of 2, we’ve made a profit. After removing twos by halfing, the remaining factors are less than the odd number we tripled-plus-one.
Longer paths tend to be chock-full of primes, like the sequence for 89 in which every odd number is a prime. Does knowing that a number is of the form 3n+1 or (3n+1)/2 tell us anthing about its prime factors? Does it help to remember that all primes are of one of two forms, either 6n+1 or 6n-1?
Well, the Collatz conjecture remains unproven for reason.