In 1937, Lothar Collatz, a German mathematician, posed the famous Collatz conjecture, which remains unsolved today. Paul Erdős has offered $500 for its solution.

**What is the Collatz Conjecture?**

Take any positive number *n*:

- If
*n*is even, divide it by two; - If
*n*is odd, triple it and add one.

In modular arithmetic notation, the function f is defined as:

Next, we form a sequence by repeating this over and over again, taking each result as the input for the next step.

The Collatz Conjecture states that:

“This process will eventually reach the number 1, regardless of which positive integer is chosen initially.”

The conjecture suggests that, regardless of the starting number, the sequence will always reach the number 1, and form a 4 – 2 – 1 loop which will repeat infinitely.

The **total stopping time** of *n *is defined as the smallest *i *such that a_{i} (the *i*th number of the sequence) is equal to one. If for some *n*, such an *i* doesn’t exist, then the conjecture is false – *n* has an infinite stopping time. However, no such *n* has been found.

**Reverse Collatz**

An alternative form of the conjecture is that 1 leads to all natural numbers using the reverse relation. However, we must remove the 1 – 2 – 4 loop (the inverse to the 4 – 2 – 1 loop). To avoid this, mathematicians substitute the relation 3n+1 of function f, by a ‘shortcut’ relation (3n+1)/2. Hence, the ‘Collatz Graph’, which is created as a result, is defined as follows:

**Proof?**

This conjecture has been checked for all starting values up to 2^{60} . However, this brute-force method will only be sufficient as proof if the conjecture is false and a counterexample is found, as we cannot check an infinite amount of numbers in finite time.

In 2011, Gerhard Opfer posted a paper that claims to prove the Collatz Conjecture. However, it was later revealed that there was a flaw in the proof.

**Importance of this Conjecture**

The Collatz conjecture is one of the simplest open problems in mathematics; you can explain to all your non-mathematical friends or even small children and they will understand it. Despite its simplicity, it relates to not only number theory, but also to topics such as:

- Chaos:
*in cellular automata*; - Decidability:
*John Conway showed that similar questions are formally undecidable*; - The foundations of mathematics and computation:
*Emil Post’s tag systems*.

When I read about this conjecture I was fascinated by its simplicity, and it reminded me of Fermat’s Last Theorem in the sense that it is easy to understand but overwhelmingly difficult to prove.

What are your favourite undecided problems in mathematics? M x

Nice Overview

A small app as download

http://www.herbert-helling.de

LikeLike

There is currently a prize of US$2,500 plus a bottle of champagne for a valid solution to this problem (or a counter-example). See

http://unsolvedproblems.org/

LikeLike

I recently proved the Conjecture. Take a look at the hypothesis here at http://wp.me/p7kaUL-b

LikeLike

Very cool!

LikeLiked by 1 person

“What’s in a name? That which we call a rose

By any other name would smell as sweet.”

-William Shakespeare (Juliet in reference to Romeo’s house)

LikeLiked by 1 person

Love that! Brilliant quote for this situation!

LikeLiked by 1 person

i have something too share from my notebook –

This conjecture was independently discovered by many mathematicians, as given on Wikipedia, so I rather call it “3x+1 conjecture” to avoid fights.

The work on this conjecture cuts across six basic areas of research:

(1) Number Theory: Analysis of periodic orbits of the map

(2) Dynamical Systems: Behaviour of generalizations of the 3x+1 map

(3) Ergodic Theory: invariant measures for generalized maps

(4) Theory of Computation: undecidable iteration problems

(5) Stochastic processes and probability theory: models yielding heuristic predictions for the behavior of iterates

(6) Computer science: algorithms for computing iterates and statistics, and explicit computations.

If possible read this beautiful paper titled “On Unsettleable Arithmetical Problems” by Conway: http://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192

LikeLike

Thank you for the correction, I must admit I was introduced to it as the Collatz Conjecture and did not research whether this was the best name.

Thank you for the link, I’ll make sure to have a read 🙂

LikeLike