collatz conjecture

The Collatz conjecture, named after Lothar Collatz (1910—1990), also known as the 3n + 1 conjecture, the Ulam conjecture after Stanislaw Ulam, or the hailstone sequence or hailstone numbers, was first stated in 1937 and concerns the following process:

Pick any positive integer n.
If n is even, divide it by two; if it is odd, multiply it by three and add one.
If n = 1, stop; else go back to step 2.

Sometimes the problem is stated differently. The termination condition ("If n = 1, stop") is removed from the procedure, so the sequence does not end. If the problem is stated this way, the conjecture becomes the statement that the sequence always ends up in the repeating loop 1, 4, 2, 1, 4, 2... This version is written using modular arithmetic as:

f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}.

For instance, starting with n = 6, one get the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1. The Collatz conjecture says that this process always reaches 1, no matter what the start value. A specific Collatz sequence can be easily computed:

  def collatz(n)    print n    if n.odd? and n > 1      collatz(3n + 1)    else if n.even?      collatz(n / 2)

Supporting arguments

The conjecture has been checked by computer for all start values up to 3 × 2⁵³ = 27,021,597,764,222,976, but a proof of the conjecture has not been found. Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution. There are some heuristic, statistical arguments supporting the conjecture: if one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they eventually hit the bottom.

Other ways of looking at it

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,

R(n) = \begin{cases} 2n & \mbox{if } n\equiv 0,1 \\ 2n, (2n-1)/3 & \mbox{if } n\equiv -1 \end{cases} \pmod{3}.

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).

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 :

f(n, d) = \begin{cases} (3n + d + 1)/2d  & \mbox{if } 3n + d + 1 < 2d \\

(3n - d + 1)/4d & \mbox{if } 3n + d + 1 \ge 2d \end{cases} (n = numerator; d = denominator) 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.

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 three steps on any odd number until only one "1" remains :

Add the original to the original with a "1" appended to the end.
Remove all trailing "0"s.
Repeat until the string length is one.

Optimizations

If n is a multiple of 4, it can be divided by 4.

Reason: It is initially even. When it is divided by two, it is still even.

If n is odd, 3n + 1 is even.

If n is odd, one step can be skipped by finding (3n + 1) / 2
Reason: an odd times an odd is always an odd (neither contributes a factor of 2 and without a 2, it cannot be even), so 3n is odd.
For instance: 3 × 35 + 1 = 106

3m + 1 is guaranteed to be in the Collatz sequence of 4m + 1.

If n ≡ 1 (mod 4), n can be converted to (n - 1) / 4 as many times as possible, saving a step every time this conversion is done. Whatever number is left, even or odd, will then be converted to 3n + 1.
Reason: 4m + 1 is always odd, so it will turn into 3(4m + 1) + 1 = 12m + 4 = 4(3m + 1) and then can be divided by two twice.
For instance: 405 can be converted: 405 → 101 → 25 → 6 → 19. The normal Collatz sequence also contains 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19

The above facts can be used to create a new version of the Collatz function :

f(n) = \begin{cases}

n / 4 & \mbox{if } n \equiv 0 \\ 3 g\left( (n-1)/4 \right) +1 & \mbox{if } n \equiv 1 \\ n / 2 & \mbox{if } n \equiv 2 \\ (3n+1)/2 & \mbox{if } n \equiv 3 \end{cases} \pmod{4}