Collatz Conjecture

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:

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

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 ai (the ith 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.

Total stopping time of numbers from 1 – 9999 | Source: Wikipedia
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:

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

Collatz Graph | Source: jasondavies.com
Proof?

This conjecture has been checked for all starting values up to 260 . 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

8 thoughts on “Collatz Conjecture”

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

    Like

    Reply

    1. 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 🙂

      Like

      Reply

Leave a comment