A Solution to the 3x + 1 Problem
David C. Kay

Abstract

The author makes the claim to have a solution for the famous 3x + 1 problem. The key to its solution is a special proof that the term (3 + ε)r is a non-integer, as well as the use of properties of extremal points of a Collatz sequence.

Keywords

Share and Cite:

Kay, D. (2023) A Solution to the 3x + 1 Problem. American Journal of Computational Mathematics, 13, 371-377. doi: 10.4236/ajcm.2023.132020.

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

$L={0}^{{s}_{0}}{1}^{{r}_{1}}{0}^{{s}_{1}}{1}^{{r}_{2}}{0}^{{s}_{2}}\cdots {1}^{{r}_{i}}{0}^{{s}_{i}}\cdots$ (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 $L={x}_{1},{x}_{2},\cdots ,{x}_{i},\cdots$ , iff a Collatz sequence $C\left(n\right)=\left\{{n}_{1},{n}_{2},\cdots ,{n}_{i},\cdots \right\}$ 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

$‖L‖={3}^{r}/{2}^{k}$ (2)

It was established in [1] that a generator can be constructed for a given finite string ${0}^{{s}_{0}}{\text{1}}^{{r}_{\text{1}}}{0}^{{s}_{\text{1}}}{\text{1}}^{{r}_{\text{2}}}{0}^{{s}_{\text{2}}}\cdots {\text{1}}^{{r}_{d}}{0}^{{s}_{d}}$ .; infinite strings do not always have generators, such as

$111\cdots 1\cdots$ , $000\cdots 0111\cdots$ and $010010001\cdots$

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 $L={\text{1}}^{{r}_{1}}{0}^{{s}_{1}}{\text{1}}^{{r}_{2}}{0}^{{s}_{2}}\cdots {\text{1}}^{{r}_{i}}$ and that the Collatz sequence corresponding to L is C = {n, n1, n2, …, ni, m}. Then

$m=\frac{{n}^{r}}{{2}^{k}}{\prod }_{i=1}^{r}\left(3+\frac{1}{{{n}^{\prime }}_{i}}\right)$ (3)

where the product is taken over all the odd members ${{n}^{\prime }}_{j}$ of C.

For example, consider the Collatz sequence

$C=\left\{89,134,67,101,152,76,38,19\right\}$

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

$\begin{array}{c}m=\frac{89}{{2}^{8}}\left(3+\frac{1}{89}\right)\left(3+\frac{1}{67}\right)\left(3+\frac{1}{101}\right)\left(3+\frac{1}{19}\right)\\ =\frac{89}{{2}^{4}}\frac{134}{89}\frac{101}{67}\frac{152}{101}\frac{29}{19}\\ =\frac{89}{1}\frac{134/2}{89}\frac{101}{67}\frac{152/{2}^{3}}{101}\frac{29}{19}\\ =89\frac{67}{89}\frac{101}{67}\frac{19}{101}\frac{29}{19}\\ =29\end{array}$

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 ε < 1018 such that

${\prod }_{j=1}^{r}{\left(3+\frac{1}{{n}_{j}}\right)}^{r}={\left(3+\epsilon \right)}^{r}$ (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

$m=n{\left(3+\epsilon \right)}^{r}/{2}^{k}$ (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 $J=\left\{{n}_{i}\right\}\cup \left\{{m}_{i}\right\}$ , {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,

${n}_{i}={2}^{{r}_{i}}{t}_{i}-1$ and ${m}_{i}={3}^{{r}_{i}}{t}_{i}-1$ (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:

${m}_{j}=\left[{3}^{r}{n}_{i}+{3}^{r}-{2}^{r}\right]/{2}^{r}$ (7)

or

${2}^{r}\left({m}_{i}+1\right)={3}^{r}\left({n}_{i}+1\right)$ (8)

Thus mi + 1 is divisible by 3r and ni + 1 is divisible by 2r and for certain positive integers p1 and p2,

${m}_{i}+1={3}^{r}{p}^{1}$ and ${n}_{i}+1={2}^{r}{p}^{2}$

But from (6.3), 2r(3rp1) = 3r(2rp2) and therefore p1 = p2 = ti ≥ 1 for some unique ti. Hence it follows that

${n}_{i}={2}^{r}{t}_{i}-1$ and ${m}_{i}={3}^{r}{t}_{i}-1$ .

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 $L={1}^{{r}_{i}}{0}^{{s}_{i}}$ and niLmi. Then

${t}_{i+1}=\frac{{3}^{{r}_{i}}{t}_{i}+{2}^{{s}_{i}}-1}{{2}^{{r}_{i}+{s}_{i}}}$ (9)

Proof: By hypothesis, niLiKimi, and from (7) we obtain

${m}_{i}=\frac{{3}^{{r}_{i}}{n}_{j}+{3}^{{r}_{i}}-{2}^{{r}_{i}}}{{2}^{{r}_{i}+{s}_{i}}}$ (10)

Since mi is a generator of Li+1 and ni is a generator of Li, by Theorem A

${m}_{i}={2}^{{r}_{i+1}}{t}_{i+1}-1$ and ${n}_{i}={2}^{{r}_{i}}{t}_{i}-1$ (11)

(10) becomes

${2}^{{r}_{i+1}}{t}_{i+1}-1=\frac{{3}^{{r}_{i}}\left({2}^{{r}_{i}}{t}_{i}-1\right)+{3}^{{r}_{i}}-{2}^{{r}_{i}}}{{2}^{{r}_{i}+{s}_{i}}}$

${2}^{{r}_{i+1}}{t}_{i+1}=\frac{{3}^{{r}_{i}}\left({2}^{{r}_{i}}{t}_{i}\right)-{2}^{{r}_{i}}}{{2}^{{r}_{i}+{s}_{i}}}+1=\frac{{3}^{{r}_{i}}{t}_{i}-1+{2}^{{s}_{i}}}{{2}^{{s}_{i}}}$

which is equivalent to the desired result.

Define ${U}_{i}={3}^{{r}_{i}}/{2}^{{r}_{i+1}+{s}_{i}}$ and ${V}_{i}=\left({2}^{{s}_{i}}-1\right)/{2}^{{r}_{i+1}+{s}_{i}}$ . Then (9) becomes for all i

${t}_{i+1}={U}_{i}{t}_{i}+{V}_{i}$

By successive substitution we obtain

${t}_{i+1}={\alpha }_{i}{t}_{1}+{\beta }_{i}$ (12)

where

${\alpha }_{i}={U}_{1}{U}_{2}...{U}_{i}$ and ${\beta }_{i}={U}_{2}{U}_{3}\cdots {U}_{i}{V}_{1}+{U}_{3}{U}_{4}\cdots {U}_{i}{V}_{2}+\cdots +{U}_{i}{V}_{i}{}_{-1}+{V}_{i}$ (13)

A lemma will be needed later, based on these results.

Lemma 1. In the special case $i=1$ , ${2}^{k}{\alpha }_{1}={2}^{k}{U}_{1}={2}^{{r}_{1}}{3}^{{r}_{1}}$ and ${2}^{k}{\beta }_{1}={2}^{k}{V}_{1}={2}^{{r}_{1}}\left({2}^{{s}_{1}}-1\right)$ .

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)

${m}_{2}={n}_{1}{\left(3+\epsilon \right)}^{r}/{2}^{k}$

where r = r1 + r2. It will be convenient to let g = (3 + ε)r − 3r. We then obtain

${2}^{k}{m}_{2}={n}_{1}\left(g+{3}^{r}\right)$

By Theorem A, ${m}_{2}={3}^{{r}_{2}}{t}_{2}-1$ and ${n}_{1}={2}^{{r}_{1}}{t}_{1}-1$ . Thus

${2}^{k}\left({3}^{{r}_{2}}{t}_{2}-1\right)=\left({2}^{{r}_{1}}{t}_{1}-1\right)\left(g+{3}^{r}\right)$

${2}^{k}{3}^{{r}_{2}}{t}_{2}-{2}^{k}={2}^{{r}_{1}}g{t}_{1}+{2}^{{r}_{1}}{3}^{r}{t}_{1}-g-{3}^{r}$

By (12),

${2}^{k}{3}^{{r}_{2}}\left({\alpha }_{i}{t}_{1}+{\beta }_{i}\right)-{2}^{k}={2}^{{r}_{1}}g{t}_{1}+{2}^{{r}_{1}}{3}^{r}{t}_{1}-g-{3}^{r}$

Using the Lemma we obtain

${2}^{{r}_{1}}{3}^{r}{t}_{1}+{2}^{{r}_{1}}{3}^{r}\left({2}^{{s}_{1}}-1\right)-{2}^{k}={2}^{{r}_{1}}g{t}_{1}+{2}^{{r}_{1}}{3}^{r}{t}_{1}-g-{3}^{r}$

which reduces to

${2}^{{r}_{1}}{3}^{r}\left({2}^{{s}_{1}}-1\right)-{2}^{k}=g\left({2}^{{r}_{1}}-1\right)-{3}^{r}$

which can be put in the form

${\left(3+\epsilon \right)}^{r}{n}_{1}={2}^{{r}_{1}}{3}^{r}\left({2}^{{s}_{1}}-1\right)-{2}^{k}+{3}^{r}\left({n}_{1}+1\right)$

Since n1 is odd, the right side is an even integer, from which it follows that for some integer N,

${\left(3+\epsilon \right)}^{r}{n}_{1}=2N$

Again, n1 is not even so cannot contain 2 as a factor, so we have for some integer N'

${\left(3+\epsilon \right)}^{r}=2{N}^{\prime }$

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.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

 [1] Kay, D. (2021) Collatz Sequences and Characteristic Zero-One Strings: Progress on the 3x + 1 Problem. American Journal of Computational Mathematics, 11, 226-239. https://doi.org/10.4236/ajcm.2021.113015 [2] Lagarias, J.C. (2010) The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society, Providence. https://doi.org/10.1090/mbk/078