1. Introduction
The article by Kay “Collatz Sequences and Characteristic Zero-One Strings: Progress on the 3x + 1 Problem” [1] provides the background needed here. Recall that a Collatz sequence C(n) generated by a positive integer n is defined by C(n) = {n, T(n), T[T(n)], [[T[T(j)]]], …} for each integer n, where T(n) = n/2 if n is even, and (3n + 1)/2 if n is odd.
Solving the 3x + 1 problem means proving that all Collatz sequences contain the integer 1. This is a long-standing conjecture over 50 years old, that has stubbornly resisted solution. A number of prominent mathematicians even discouraged working on it. Paul Erdȍs commented “mathematics is not yet ready for this problem” (Lagarias [2] . p. 31).
2. Previous Research
The volume of research on this problem is truly incredible. In [2] Lagarias has listed over 300 - 400 research articles written in the 1900’s and 2000’s—all devoted to solving the problem. Most research ended up including related conjectures as difficult as the original problem, and much was in the area of dynamic processes and ergotic theory. Our approach using strings is not related directly to dynamic processes or ergotic theory. The solution here involves only standard techiques of algebra, calculus, and elementary number theory.
We make use of a limited amount of past research. In particular, Lagarias [2] has pointed out that the 3x + 1 conjecture has been verified by special computer programs for all positive integers up to n* = 20 × 258 = 5.8 × 1018 (more recently to n* = 8.7 × 1018).
3. Zero-One Strings
A zero-one string is an infinite ordered string of zeroes and ones, written in the form
(1)
where, for each i, ri is the number of ones in the ith group of consecutive ones, andsi the number of zeroes in the ith group of consecutive zeroes. A positive integer n is said to generate a zero-one string
, iff a Collatz sequence
exists such that ni = xi (mod 2) for all i.
As in [1] , we refer to ni as the pre-resultant of a finite Collatz sequence C = C(n) where ni is the last odd member of C in a group to all odd members, and ni+1 = (3ni + 1)/2 the resultant. The total number of ones in a finite string L will be denoted r, the total number of zeroes s, and the length, k = r + s (not to be confused with the concept of length as used by others. The norm of L is defined as
(2)
It was established in [1] that a generator can be constructed for a given finite string
.; infinite strings do not always have generators, such as
,
and
4. Formulas for Resultants
The advantage of using strings is that explicit formulas for resultants can be readily established. For example, in [1] a general formula was given for the resultant of a string in terms of a generator. A fornula we will use here, also proved in [1] , is the following: suppose n and m are the generator and resultant of the string
and that the Collatz sequence corresponding to L is C = {n, n1, n2, …, ni, m}. Then
(3)
where the product is taken over all the odd members
of C.
For example, consider the Collatz sequence
corresponding to the string L = 1101120311, with s = 4, k = 8, and resultant m = (3 × 19 + 1)/2 = 29. The odd members of C are 89, 67, 101, and 19. Substituting into (3) produces
Applying the function f (x) = (3 + x)r where r is a positive integer and using the mean-value theorem, it can be shown that there exists a positive real number ε < 10−18 such that
(4)
It follows from (3) that if m and n are odd integers and equal the respective resultant and generator of a Collatz sequence C, then
(5)
(It was shown in [1] that ε is irrational for cycles.)
Observe that if a non-trivial cycle exists, m = n and (5) produces the necessary condition for cycles (3 + ε)r = 2k.
5. The Term (3 + ε)r
We finally prove that the term (3 + ε)r is a non-integer. Suppose there are values for the positive integer n for which (3 + ε)n is a positive integer. Take n to be the least of these; it follows that (3 + ε)n–1 is a non-integer. It follows that (3 + e)m is a non=integer for all m ≤ n – 1.
If exactly one of (3 + ε)n–1 and 3 + ε is rirational, then (3 + ε)n is irrational, a contradiction, so we conclude that either both are rational (Case (1)) or both are irrational (Case (2)). In Case (1), take (3 + ε)n–1 = x/y and 3 + ε = u/v (all integers), and with the fraction xu/yv reduced to lowest terms. Then the product xu/yv = N or xu = yvN. No prime divisor of xu can appear in yv, so ultimately we must have xu | N. Then there exists an integer N' such that N = xuN' and xu = yvxuN' or 1 = yvN'. One obtains y = v = 1 which implies the contradiction that both (3 +ε)n–1 and (3 +ε) are integers.
In Case (2) when both (3 +ε)n–1 and (3 +ε) are irrational, these two may be approximated arbitrarily closely by rationals, say by x/y and u/v. It follows that their product is approximated arbitrarily closely to the result, which is the integer N. Hence, xu/yv = N or xu = yvN. Assuming (xu, yv) = 1 as before, we obtain a contradiction as before, finally proving that (3 +ε)u cannot be an integer.
This leaves N = a non-integer, a contradiction. The contradictions prove that the term (3 + ε)n is a non-integer for all integers n, leading to the desired result.
It follows that (3 + ε)r ≠ 2k and we have the proof that non-trivial cycles do not exist. It remains to prove that a Collatz sequence not containing 1 also does not exist.
6. Extreme Points of a Collatz Sequence
The graph of any Collatz sequence reveals the existence of a sub-sequence consisting of extreme points
, {ni} the minimal extreme points and {mi} the maximal extreme points. These numbers obey the basic inequalities mi > ni for each i ≥ 1. Furthermore, each ni is the generator of a Collatz sequence of all odd integers.
The following result provides more information concerning extreme points.
Theorem A. There exists a unique sequence of positive integers {ti} (to be called the pre-extremal sequence) such that for each i,
and
(6)
Proof: Since mi is the resultant of the Collatz sequence of r odd numbers, r ≥ 1, the following identity can be routinely established by induction on r:
(7)
or
(8)
Thus mi + 1 is divisible by 3r and ni + 1 is divisible by 2r and for certain positive integers p1 and p2,
and
But from (6.3), 2r(3rp1) = 3r(2rp2) and therefore p1 = p2 = ti ≥ 1 for some unique ti. Hence it follows that
and
.
as desired.
For a numerical example, consider the Collatz sequence C generated by n = 195 and corresponding string L = 12031302140111 written as L1K1L2K2L3K3L4, where L1 = 11, K1 = 000, L2 = 111, K2 = 00, L3 = 1111, K3 = 0, and L4 = 1. Note that 195 is uniquely preceded by 390, so J begins with 195, a local minimum. The members of C can be written as follows, with the members of J in bold type:
C(195) = {195, 293, 440, 220, 110, 55, 83, 125, 188, 94, 47, 71, 107, 161, 242, 121}
and we have
195(11)440(000)55(111)188(00)47(1111)242(0)121(1)
with
195 = 22(49) − 1
440 = 32(49) − 1
55 = 23(7) − 1
188 = 33(7) − 1
47 = 24(3) − 1
242 = 34(3) − 1
121 = 21(61) − 1
In this case, the pre-extremal sequence is {49, 7, 3, 61}.
We observe the following algorithm that generates the sequence {ti} Since ni is odd, add 1 to make it even, and begin dividing by 2 until an odd number u appears. This odd number u can be taken as ti since ni + 1 = 2vu or ni = 2vu − 1. The following result is also clear from this analysis:
Theorem B. The pre-extremal sequence consists of all odd integers.
7. A Formula for ti+1 in Terms of t1
Theorem A leads to a formula for ti+1 in terms of t1. A preliminary result is needed first.
Theorem C. Let
and niLmi. Then
(9)
Proof: By hypothesis, niLiKimi, and from (7) we obtain
(10)
Since mi is a generator of Li+1 and ni is a generator of Li, by Theorem A
and
(11)
(10) becomes
which is equivalent to the desired result.
Define
and
. Then (9) becomes for all i
By successive substitution we obtain
(12)
where
and
(13)
A lemma will be needed later, based on these results.
Lemma 1. In the special case
,
and
.
The proof is a routine result in algebra and will be omitted.
8. Divergent Strings
A divergent string is a string of zeros and ones not ending in 1010…
Theorem D. A divergent string has no generator.
Proof: Suppose L is a divergent string with a generator n, and with corresponding Collatz sequence C = C(n). Then C cannot contain a 1 or L ends in 1010… Every member of C is then greater than n* and there exists a least generator n' > n* of C. Hence, n' = n1 is an (odd) minimal extreme point of C, followed by an (even) maximal extreme point m1, which is the resultant of r1 odd members of C and generator of s1 even members of C, followed by n2, generator of r2 odd members of C, ending with m2, a maximal extreme point (even), the resultant of r2 odd members of C. There are a total of r1 + s1 + r2 = k members of C listed here (in other words a smaller Collatz sequence C', of which n1 is a generator and m2 the resultant). By (5)
where r = r1 + r2. It will be convenient to let g = (3 + ε)r − 3r. We then obtain
By Theorem A,
and
. Thus
By (12),
Using the Lemma we obtain
which reduces to
which can be put in the form
Since n1 is odd, the right side is an even integer, from which it follows that for some integer N,
Again, n1 is not even so cannot contain 2 as a factor, so we have for some integer N'
which violates the result of Section 5, showing that L has no generator.
9. Conclusion
The 3x + 1 problem has been proved in the affirmative, establishing that a finite Collatz sequence always converges to 1.