Collatz conjecture
The Collatz conjecture[a] is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×1020, but no general proof has been found.
It is named after the mathematician Lothar Collatz, who introduced the idea in 1937, two years after receiving his doctorate.[4] The sequence of numbers involved is sometimes referred to as the hailstone sequence, hailstone numbers or hailstone numerals (because the values are usually subject to multiple descents and ascents like hailstones in a cloud),[5] or as wondrous numbers.[6]
Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[7] Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics".[8]
Consider the following operation on an arbitrary positive integer:
In modular arithmetic notation, define the function f as follows:
Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.
In notation:
(that is: ai is the value of f applied to n recursively i times; ai = f i(n)).
The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially. That is, for each , there is some with .
If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence would either enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.
The smallest i such that ai < a0 is called the stopping time of n. Similarly, the smallest k such that ak = 1 is called the total stopping time of n.[2] If one of the indexes i or k doesn't exist, we say that the stopping time or the total stopping time, respectively, is infinite.
The Collatz conjecture asserts that the total stopping time of every n is finite. It is also equivalent to saying that every n ≥ 2 has a finite stopping time.
Since 3n + 1 is even whenever n is odd, one may instead use the "shortcut" form of the Collatz function:
This definition yields smaller values for the stopping time and total stopping time without changing the overall dynamics of the process.
Extensions to larger domains
Iterating on all integers
An extension to the Collatz conjecture is to include all integers, not just positive integers. Leaving aside the cycle 0 → 0 which cannot be entered from outside, there are a total of four known cycles, which all nonzero integers seem to eventually fall into under iteration of f. These cycles are listed here, starting with the well-known cycle for positive n:
Odd values are listed in large bold. Each cycle is listed with its member of least absolute value (which is always odd) first.
Optimizations
Time–space tradeoff
The section As a parity sequence above gives a way to speed up simulation of the sequence. To jump ahead k steps on each iteration (using the f function from that section), break up the current number into two parts, b (the k least significant bits, interpreted as an integer), and a (the rest of the bits as an integer). The result of jumping ahead k is given by
If k is an odd integer, then 3k + 1 is even, so 3k + 1 = 2ak′ with k′ odd and a ≥ 1. The Syracuse function is the function f from the set I of positive odd integers into itself, for which f(k) = k′ (sequence A075677 in the OEIS).
Some properties of the Syracuse function are:
The Collatz conjecture is equivalent to the statement that, for all k in I, there exists an integer n ≥ 1 such that fn(k) = 1.
In popular culture
In the movie Incendies, a graduate student in pure mathematics explains the Collatz conjecture to a group of undergraduates. She puts her studies on hold for a time to address some unresolved questions about her family's past. Late in the movie, the Collatz conjecture turns out to have foreshadowed a disturbing and difficult discovery that she makes about her family.[35][36]