Collatz Conjecture

From Mathsreach

Jump to: navigation, search

Take any positive integer; if even, divide by two; if odd, triple it and add one. Using each result as the
input for the next step, no matter what number starts the sequence, the end result is 1.

Simply: That all paths in a certain kind of number sequence eventually lead to 1.
Also known as: The 3n + 1 conjecture, the Ulam conjecture (after Polish mathematician Stanislaw Ulam), the
Syracuse problem or HOTPO (Half Or Triple Plus One) in computer programming.

Discipline: Number theory.

Originator: German mathematician Lothar Collatz, 1937; he made very little progress and published a history
of its origin much later.

Incentive: $US50 by H Coxeter, 1970; then $US500 by Hungarian mathematician Paul Erdős; £1,000 by B
Thwaites, 1996; solving a problem with a tantalizingly elementary form that has eluded top mathematicians.

Examples: If n = 6, the number sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1. If n = 27, the sequence takes 111 steps,
climbing to over 9,000 before descending to 1.

Explorations: Many attempts have been made to settle the conjecture using technologies from number theory,
dynamical systems and Markov chains. USA mathematician Jeffrey Lagarias proved in 1985 that the problem
has no nontrivial cycles of length <275,000. Another approach took the opposite direction; instead of proving
that all natural numbers eventually lead to 1, it proved that 1 leads to all natural numbers. USA mathematician
John Conway proved in 1972 that Collatz-type problems can be formally undecidable.

State of play: Although the conjecture has not been proved, most mathematicians who have worked on the
problem believe it is true. The conjecture has been checked by computer for all starting values up to 10 × 258.
However, some important conjectures have been found to be false only with very large counterexamples.
Each odd number in Collatz sequences is on average ¾ of the previous one, leading to an argument that
every Collatz sequence should decrease in the long run. This is also not a proof because it pretends that the
sequences are assembled from uncorrelated probabilistic events.

Published in IMAges 5 - November 2008