Collatz Conjecture Remains Unproven Despite its Easy Arithmetic

Lothar Collatz Image by Konrad Jacobs

Lothar Collatz proposed the “Collatz problem” in 1937. It is still an unproven conjecture. Although it has not been disproved, neither is there an accepted proof.

Defining the Collatz Function and Series

A neat and tidy mathematical description of the problem is:

Let “n”, “i”, “j” and “m” be any positive integers, and define a function f(n):

f(n)=3*n + 1, if “n” is odd (( and greater than 1 ))
f(n)=n/2, if “n” is even

Then define a series a[j] of positive integers, where

a[1]=m for an arbitrary positive integer “m”, and
a[i+1]=f(a[i])

What Does The Collatz Conjecture Really Mean?

Here is an English description. First, we define a function on a positive integer, “n”, that has two rules. If “n” is odd, multiply “n” by three and then add one. If “n” is even, divide “n” by two. Let’s call this whole function “f(n)”.

Second, we create a series of positive integers. Choose any positive integer as the starting number. Create the next number in the series by applying that two-rule function “f(n)” to the current number in the series.

It would be decent of us to point out that the series is really boring if you start with “1″. It simply repeats “1, 4, 2, 1, 4, 2, 1, 4, 2, 1…” forever.

Collatz Sample Image by Mike DeHaan

The Collatz Conjecture

Come to think of it, starting with either “2″ or “4″ gives exactly the same sequence, only with a different starting point.

So let’s start with “3″. We find {3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1…}. The “same old, same old” final repeating sequence finishes this off. Obviously, starting with “5″ would just be a shortcut into this sequence.

Collatz conjectured that starting with any positive integer would eventually end with this repeating sequence. That is to say, he believed it to be true but could not prove it with mathematical rigor.

The article “Lothar Collatz“, dated 2006, states that this had been verified for numbers up to about 10^14 (100,000,000,000,000). Of course, this evidence does not count as proof; we simply have not yet found a counter-example.

More recently, “The easiest math conjecture it took 74 years to prove” told of an proof that was later “withdrawn”. The problem was on page 11 of 32, according to the author’s note on the pre-print PDF.

Observations about the Collatz Conjecture’s Series

Let’s think about the function “f(n)” with its two rules. What can we notice about it?

My first thought is, “An odd number increases more than 1.5 times faster than an even number decreases”. That’s because of the factors “3″ and “2″ in “3*n” versus “n/2″.

But then, every time we have an odd number, the next number is even. That’s because of the “+ 1″ in “3*n + 1″. So the “3*n” increase can only happen once before the “n/2″ rule decreases the value.

How frequently is the “n/2″ rule repeated before we can make the number bigger with “3*n + 1″? Every even integer, “e”, can be written as “e=m*2″. Half of all integers are even; the others are odd. So, if the Collatz conjecture’s sequence just happens to be random, half the time we would use the “n/2″ rule once because that even number factors into 2 and an odd number. But the other half of the time, it factored into 4 (or a higher power of 2) and an integer. So we might expect “on average” to mulitply a number in the Collatz series by 3/4…or less.

Starting with “6″ just brings us back to “3″. In fact, starting with any even number “e” gives the same final sequence as starting with “e/2″.

Finally, if the series lands on a power of 2, then the series collapses directly to 1. If n=2^m, then dividing by 2 means that the next number in the Collatz series is 2^(m-1), down to 2^0=1.

Collatz Graph Image by TerrorBite

Approaches to Proving the Collatz Conjecture

Let’s keep the definitions of the functions and the series as shown earlier. The cumbersome but accurate question is ‘For any positive integer “m”, does setting a[1]=m always result in a[n]=1 where “n” is a finite integer’?

Avoid the Halting Problem

Unfortunately this question has the phrase “finite integer” in a problem about generating a series. That reminds me of the theory of computing problem called the “halting problem.” It asks whether a particular computer program, given finite input, would eventually finish a calculation or just keep going forever.

The Collatz series is very similar to a computer program that would stop when it produces the “1″ result. Will this program stop?

Alan Turing had proven that, in general, one cannot write a computer program to determine whether any other arbitrary program would halt or keep running forever. I don’t know whether the program for the Collatz series would qualify as an “undecidable halting” instance.

According to Weisstein in “Collatz Problem“, it has been proven that “a natural generalization of the Collatz problem is undecidable”. That means the generalized form can neither be proven nor disproved. However, “this proof cannot be applied to the original Collatz problem”. So it is a safe bet that the “halting problem” does not cut through this Gordian knot.

Ask Another Question About the Collatz Function

Producing the “1″ result in the series is the same as producing a power of two. That is because applying the Collatz function to a power of two will only invoke the “n/2″ rule until the series winds down to “1″ and begins repeating.

So let’s examine “3*n + 1″ from that perspective. Certainly “3*n + 1″ always creates an even number. If the conjecture has been tested through 2^14, then there are many cases where 3*n + 1 = 2^m for some integer “m”. But there are many cases where it does not. This does not lead to a quick solution.

Can Set Theory Help with the Collatz Conjecture?

The “set version” of the Collatz conjecture could be described as: “There is a (large) set of numbers, C, to start the Collatz series that satisfy the conjecture. Is C the same as I, the set of positive integers?”

Another way of asking the same question is to define the set C’ as the initial numbers that disprove the Collatz conjecture. Is that set, C’, empty?

Does Assuming the Opposite Lead to a Contradiction?

Typically this approach would say, ‘Suppose there is a starting number, “n”, such that the Collatz series does not return to “1″. This would disprove the Collatz conjecture. The following discussion shows that this leads to a contradiction. That contradiction proves that the Collatz conjecture must be true’.

A previous article, “A Quick Explanation of Mathematical Induction“, showed how an incorrect assumption could lead to a contradictory result.

This is a terrific approach…if only we could prove that a contradiction does follow from such an assumption.

Current Status of the Collatz Conjecture

As noted, this conjecture has not yet been proven (as of June 27, 2011).  It is a live topic in mathematics, so the status could change at any time.

The Collatz Fractal Image

The Collatz series can be extended to negative integers, real numbers and complex numbers. “Pokipsy76″ created this fractal image and gives a brief description in the Wikipedia article “File:CollatzFractal.png“.

"Collatz Fractal" Image by Pokipsy76

A Quick Biography of Lothar Collatz

Lothar Collatz was born July 6, 1910 in Arnsberg, Westphalia, Germany. He studied at several German universities, gaining a doctorate with a thesis about the finite difference method applied to linear differential equations. He taught at the universities of Hanover and of Hamburg.

He wrote over two hundred papers, several important books and texts. He died in Bulgaria while attending a conference.

References:
JOC/EFR, University of St Andrews, Scotland, “Lothar Collatz“, Nov. 2006, referenced June 26, 2011.
Esther Inglis-Arkell, io9, “The easiest math conjecture it took 74 years to prove“, published June 21, 2011, referenced June 26, 2011.
Gerhard Opfer, Hamburger Beitrage zur Angewandten Mathematik, “An analytic approach to the Collatz 3n + 1 Problem“, May 2011 (withdrawn June 17, 2011), PDF referenced June 26, 2011.
Weisstein, Eric W, MathWorld, “Collatz Problem“, referenced June 26, 2011.

Tweet

Tags: Collatz conjecture, Collatz function, collatz problem, Collatz series, lothar collatz