number collatzing

[_rck_]

I spent part of the afternoon thinking about the Collatz(3n+1) conjecture (suggested to me by the Wikipedia article on proof of impossibility). I purposefully decided not to read the article one on the conjecture itself, but rather to play around with the problem a bit instead.

Briefly put, the Collatz conjecture applies a rule for converting one positive integer into another until you are told to stop. The rule is very simple:

1. If the number is 1, stop (no more conversions).
2. If the number is even, divide by two.
3. If the number is odd, multiply by three and add one.

Some examples? Here are the Collatz results for the first couple of primes:

[2, 1] [3, 10, 5, 16, 8, 4, 2, 1] [5, 16, 8, 4, 2, 1] [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Notice that the Collatz sequence for 13 is a sub-sequence for the Collatz sequence of 11, which in turn is a sub-sequence of the Collaz sequence of 7. Ditto for 5 being a sub-sequence of 3.
The conjecture is that for any positive natural number, this algorithm will terminate; but no one has been able to prove that. The article on proof of impossibility gives two clues for believing that the conjecture is true, and one against.

My analysis so far has been (and this may be completely redundant with what everybody else on the web said, because I purposefully did not look):

• The underlying structure of the algorithm is dictated by prime factorization. There are basically three classes of numbers:
  1. Numbers that are a product of odd primes only (e.g. 35).
  2. Numbers that are powers of two (i.e. product of the one even prime only) (e.g. 32).
  3. Numbers that are even and have one or more odd prime factor (e.g. 12).
• If the number is a power of two, the proof that this will terminate follows by mathematical induction from the part of the rule for even numbers and the stop condition.
• If the number is even (but not a power of two), the algorithm strips all factors of two off until the result is a member of the first group of odd prime factors only. Thus, one can reduce the problem to asking whether one can show that this algorithm terminates for all products of odd primes.
• If the number is odd (a product of odd primes only), then the rule will make it even, sometimes into a power of two (e.g. 5 => 16), sometimes not (7 => 22 => 11 ...).

In order to get a better idea of how this all works, I decided to build a little Python program that computes the Collatz sequence for a given number. The decisive point seems to be how the number of odd prime factors gets transformed into another set of prime factors, some of which will be even and disappear. Consider the following sequence:

[35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
If one looks at the factorization of the first couple of numbers, one gets the following:

35: [5, 7] 106: [2, 53] 160:[2, 2, 2, 2, 2, 5]
One way to disprove the conjecture would be to find a combination of factors that, when fed to the 3n+1 formula, produce either a cycle or an expansion that adds more odd primes, basically pumping the number up ad infinitum. Alternatively, if one could prove that neither a cycle or an expansion were possible, then the conjecture would of course hold.

At this point in time, my thinking is that for either approach one would have to have a constructive understanding of the primes, i.e. something other than the sieve, which allows one to write composite formulas for (odd) primes. This might permit tracing through the transformation function that maps odd factor set to odd factor set to show that the properties enumerate can or cannot arise. But (and here I checked on the web), since we do not have a constructive understanding of the primes, we wont be able to take that route.

Well, I had fun, anyways.