Collatz conjecture: Encyclopedia II - Collatz conjecture - Other ways of looking at it

Collatz conjecture - Other ways of looking at it

Collatz conjecture - In reverse

There is another approach to prove the following conjecture, which considers the bottom-up method of growing the Collatz graph. The Collatz graph is defined by an inverse relation,

So, instead of proving that all natural numbers eventually lead to 1, we can prove that 1 leads to all natural numbers. Also, the inverse relation forms a tree except for the 1-2 loop. Note that the relation being inverted here is (3n + 1) / 2 (see Optimizations below).

Collatz conjecture - As rational numbers

The natural numbers can be converted to rational numbers in a certain way. To get the rational version, find the highest power of two less than or equal to the number, use it as the denominator, and subtract it from the original number for the numerator (527 → 15/512). To get the natural version, add the numerator and denominator (255/256 → 511).

The Collatz conjecture then says that the numerator will eventually equal zero. The Collatz function changes to :

This works because 3x + 1 = 3(d + n) + 1 = (2d) + (3n + d + 1) = (4d) + (3n - d + 1). Reducing a rational before every operation is required to get x as an odd.

Collatz conjecture - As an abstract machine

Repeated applications of the Collatz function can be represented as an abstract machine that handles strings of bits. The machine will perform the following two steps on any odd number until only one "1" remains :

1. Add the original with a "1" appended to the end, to the original .
2. Remove all trailing "0"s.

Collatz conjecture - As iterating a real or complex map

The Collatz map can be looked as a restriction to the integers of the smooth real and complex map

(Note that the restriction of f to integer values is not the standard Collatz map defined above, it is an "optimization", see "optimizations" below.) Iterating the map in the complex plane produces the Collatz fractal.

Adapted from the Wikipedia article "Other ways of looking at it", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki