A problem posed by L. Collatz in 1937, also called Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problem (Lagarias 1985).
The Collatz problem can be simply stated. Starting from a positive integer n, apply the following function:
Can you prove or disprove that you will ultimately reach 1. Another way of phrasing this question is to consider the sequence a0, a1, a2, ..., an where a0 is the initial seed for the collatz function and try to find a repeating sequence that does not contain 1 (the only sequence yet found in coll(n) is (2-1-)*.
Erdos stated (according to Lagarias) that because of the difficulty in solving this problem, "mathematics is not yet ready for such problems". In other words, don't expect to solve this problem, but have fun trying.
Consider a sub-sequence n1, n2, ..., nk within a collatz sequence. It is straightforward to construct a sequence of any length that (a) does not contain a cycle; and (b) does not contain the number 1.
| Lemma 1. Given positive integer k, there is a
number n such that k applications of coll(n) do not lead to
1.
Proof. Consider the number n=q*2k, where q is a positive integer greater than 1. One can apply coll() k times, because the factor 2 appears k times in the prime factorization of n. The resulting number is q, which by definition is greater than 1. |
What about when n is an odd number?
| Lemma 2. Given positive integer k>1, there exists
a number n such that k applications of coll(n) do not lead to 1.
Proof. Consider the odd number n=2k-1 greater than 1. By definition, coll(n) = (3*(2k-1)+1)/2. Simplifying this equation leads to (3*2k-2)/2, which equals 3*2(k-1)-1. The numbers 2 and 3 are not divisors of this number, because of the general theorem of divisors in number theory which shows that if prime p | n, then p does not divide (n-1). After c applications of coll(), the resulting number is 3c*2(k-c)-1, which will be an odd number not divisible by 3. After k applications of coll(), the resulting number is 3k-1, which is guaranteed to be an even number. Since 3k-1 is greater then 2k-1, we have a sequence of increasing numbers all greater than 1. |
Other definitions. Define Ci = { n | takes i steps to get to 1 using coll(n) }. Ci is the finite set of numbers that effectively form the "row" of an infinite tree rooted at 1 with two types of edges, a left branch from n to (2*n-1)/3 if this value is an integer, and a right branch always exists from n to 2*n.
maxi = Max (Ci) = 2i
There seems to be no easy formula for mini. But for i>4 you can show that 3*mini+2(i-4) is a member of Ci.