Collatz Conjecture

Post Reply New Topic

Try this one:
Here is the Rule:
Given an integer n, if n = 1 then stop
If n is odd and greater than 1, then compute (3*n + 1)/2
If n is oven then compute n/2.

Show the following: Given any integer N > 1 and apply the Rule interatively you will eventually stop at 1. .

This is called the Collatz Conjuecture in the math literature. If you can prove the above theorem you will become very, very famous. It has been an open problem since about 1950 when it was first proposed.

ruveyn

Obviously strong induction is needed. The details of putting it together get rather messier.

Here's a try at a general outline, or just some rambling observations that might be relevant to a proof attempt.

(3n+1)/2 must be either even or odd. If it is even, divide again by 2 (by the rule) so you have, in effect, (3n+1)/4, and (3n+1)/4 < n for all n greater than 1.

If (3n+1)/2 is odd, then you have (3((3n+1)/2)+1)/2 = (9n+5)/4. (Assuming I didn't mess up my arithmetic there)

Hm. Yeah, I'm not really getting anywhere. This Collatz is a tricky little bastard. I can see plainly enough that the defined operations will give you a decreasing string of numbers, and that should eventually end up at 1, but I don't see a nice rigorous proof of what is intuitively obvious.

As an aside, does anyone know how to post LaTeX on WP?

Welcome to the Club. The late Paul Erdos was a member also.

The Collatz is as hard a nut to crack was Fermat's (so-called) Last Theorem, which was not a theorem until Wiles proved it.

ruveyn

I use LaEqEd - Latex Equation Editor.

It ends up with the latex embedded in a PNG image of the result. You upload the image (somewhere), and anyone else can then grab it, and mess with the latex source that made it. Java.

May one ask what the use of this is?

It's not normally considered etiquette to question a mathematician on the application of their studies.

You mean, it's quite useless.

One cannot predict what practical applications will flow from attempts to resolve the conjecture. For example, the work on proving Fermat's Last Theorem gave rise to some techniques that were later used in cryptography. Ditto for number theory. Private-Key Public-Key cryptography is a direct application of pure number theory.

When B. Riemann developed the generalized theory of curvature in space, who know that someday the GPS would be an application of his work by way of the General Theory of Relativity by Einstein?

ruveyn

Of what use is a newborn baby? - Benjamin Franklin, on balloons...

I think it was P.M. Gladstone who asked Michael Faraday what use his electromagnetic force was. Faraday answered: Some day you will tax it.

ruveyn

To get back on topic..

If you can "... can see plainly enough that the defined operations will give you a decreasing string of numbers..." then you'd better put it down on paper (pixels), before you lose the image.

It certainly does seem that most of the time, all you need examine is a widening spread of "power of two" types of numbers, and each time, just in one instance out of the 2^n cases, sneakily keeps on increasing.

In some ways, Collatz could be said to be just as easy as proving that every point on a line must be representable as p/q, where p and q are integers. A statement that seems pretty sound, to start with...

Anyway, from http://en.wikipedia.org/wiki/Collatz_conjecture

Now, this is something you can talk about. Mathemathicians on the other hand dont bother to talk in normal language.
I think mathematicians like this, sort of being part of a secret society.

What secrets? Mathematics is literally an open book. The only entrance requirement is the willingness and ability to work at developing the skill.

ruveyn

The reason for the specialized terminology is because "normal" language does not have appropriate words to describe the concepts we need in mathematics, and when it does have words they are not precise enough.

The Collatz Conjecture seems interesting. If it is true then I wonder how it would eventually be proven. If it is as difficult to prove as Fermat's Last Theorem was, then it will probably take some time before it happens.