Collatz conjecture
|
|
The Collatz conjecture is an unresolved conjecture in mathematics. It is named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanislaw Ulam), the Syracuse problem, or the hailstone sequence or hailstone numbers. It asks whether a certain kind of number sequence always ends in the same way, regardless of the starting number.
Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution.
| Contents |
Statement of the problem
Consider the following operation on an arbitrary positive integer:
- If the number is even, divide it by two.
- If the number is odd, triple it and add one.
For example, if this operation is performed on 3, the result is 10; if it is performed on 28, the result is 14.
In mathematical notation, define the function f as follows:
- <math> f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}. <math>
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:
- <math> a_i = \begin{cases}n & \mbox{for } i = 0 \\ f(a_{i-1}) & \mbox{for } i > 0\end{cases}<math>
The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially. Or, more rigorously:
- <math> \forall n > 0 : \exists i : a_i = 1 <math>
If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence which does not contain 1. Such a sequence might enter a repeating cycle that excludes 1, or increase without bound; no such sequence has been found.
Examples
For instance, starting with n = 6, one gets the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4 ... The Collatz conjecture says that this process always reaches 1, no matter what the starting value.
Starting with n = 11, the sequence takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
If the starting value n = 27 is chosen, the sequence takes 114 steps, climbing above 9,000, before descending to 1.
Program to calculate Collatz sequences
A specific Collatz sequence can be easily computed, as is shown by this pseudocode example:
def collatz(n)
print n
if n.odd? and n > 1
collatz(3n + 1)
else if n.even?
collatz(n / 2)
This program halts when the sequence reaches 1, in order to avoid printing an endless cycle of 4, 2, 1. If the Collatz conjecture is true, the program will always halt no matter what positive starting integer is given to it. (See Halting problem for a discussion of the relationship between open-ended computer programs and unsolved mathematics problems.)
Supporting arguments
Although the conjecture has not been proven, most mathematicians who have looked into the problem believe intuitively that the conjecture is true. Here are some reasons for expecting this.
Experimental evidence
The conjecture has been checked by computer for all start values up to 3 × 253 = 27,021,597,764,222,976. Intuitively, it would be surprising if the smallest counterexample were larger than this large number. As computers speed up and testing techniques improve, this testing horizon will continue to increase.
Probabilistic evidence
If one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they should decrease in the long run.
Other ways of looking at it
In reverse
There is another approach to prove the following conjecture, which considers the bottom-up method of growing the Collatz graph. The Collatz graph is defined by an inverse relation,
<math> R(n) = \begin{cases} 2n & \mbox{if } n\equiv 0,1 \\ 2n, (2n-1)/3 & \mbox{if } n\equiv -1 \end{cases} \pmod{3}. <math>
So, instead of proving that all natural numbers eventually lead to 1, we can prove that 1 leads to all natural numbers. Also, the inverse relation forms a tree except for the 1-2 loop. Note that the relation being inverted here is (3n + 1) / 2 (see Optimizations below).
As rational numbers
The natural numbers can be converted to rational numbers in a certain way. To get the rational version, find the highest power of two less than or equal to the number, use it as the denominator, and subtract it from the original number for the numerator (527 → 15/512). To get the natural version, add the numerator and denominator (255/256 → 511).
The Collatz conjecture then says that the numerator will eventually equal zero. The Collatz function changes to :
- <math> f(n, d) = \begin{cases} (3n + d + 1)/2d & \mbox{if } 3n + d + 1 < 2d \\
(3n - d + 1)/4d & \mbox{if } 3n + d + 1 \ge 2d \end{cases} <math> (n = numerator; d = denominator)
This works because 3x + 1 = 3(d + n) + 1 = (2d) + (3n + d + 1) = (4d) + (3n - d + 1). Reducing a rational before every operation is required to get x as an odd.
As an abstract machine
Repeated applications of the Collatz function can be represented as an abstract machine that handles strings of bits. The machine will perform the following three steps on any odd number until only one "1" remains :
- Add the original to the original with a "1" appended to the end.
- Remove all trailing "0"s.
- Repeat until the string length is one.
Optimizations
If n is a multiple of 4, it can be divided by 4.
- Reason: It is initially even. When it is divided by two, it is still even.
If n is odd, 3n + 1 is even.
- If n is odd, one step can be skipped by finding (3n + 1) / 2
- Reason: an odd times an odd is always an odd (neither contributes a factor of 2 and without a 2, it cannot be even), so 3n is odd.
- For instance: 3 × 35 + 1 = 106
3m + 1 is guaranteed to be in the Collatz sequence of 4m + 1.
- If n ≡ 1 (mod 4), n can be converted to (n - 1) / 4 as many times as possible, saving a step every time this conversion is done. Whatever number is left, even or odd, will then be converted to 3n + 1.
- Reason: 4m + 1 is always odd, so it will turn into 3(4m + 1) + 1 = 12m + 4 = 4(3m + 1) and then can be divided by two twice.
- For instance: 405 can be converted: 405 → 101 → 25 → 6 → 19. The normal Collatz sequence also contains 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19
The above facts can be used to create a new version of the Collatz function :
- <math> f(n) = \begin{cases}
n / 4 & \mbox{if } n \equiv 0 \\ 3 g\left( (n-1)/4 \right) +1 & \mbox{if } n \equiv 1 \\ n / 2 & \mbox{if } n \equiv 2 \\ (3n+1)/2 & \mbox{if } n \equiv 3 \end{cases} \pmod{4} <math>
- <math> g(n) = \begin{cases} n & \mbox{if } n \;\not\equiv\; 1 \\
g \left( (n-1)/4 \right) & \mbox{if } n \equiv 1 \end{cases} \pmod{4}. <math>
See also
References and external links
- Jeff Lagarias: The 3x + 1 problem and its generalizations (http://www.cecm.sfu.ca/organics/papers/lagarias/), American Mathematical Monthly Volume 92, 1985, pp. 3 - 23.
- An ongoing distributed computing project (http://personal.computrain.nl/eric/wondrous/index.html) verifies the Collatz conjecture for larger and larger values.
- Collatz Problem (http://mathworld.wolfram.com/CollatzProblem.html) on MathWorld
de:Collatz-Problem fr:Conjecture de Syracuse ko:콜라츠 추측 it:Congettura di Collatz pl:Problem Collatza zh:角谷猜想