A Solution to the 3x + 1 Problem

David C. Kay

Weaverville, NC, USA.

DOI: 10.4236/ajcm.2023.132020                

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

Collatz Sequences, Extreme Points, Pre-Extreme Sequence

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 × 2⁵⁸ = 5.8 × 10¹⁸ (more recently to n* = 8.7 × 10¹⁸).

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, r_i is the number of ones in the ith group of consecutive ones, ands_i 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 n_i = x_i (mod 2) for all i.

As in [1] , we refer to n_i as the pre-resultant of a finite Collatz sequence C = C(n) where n_i is the last odd member of C in a group to all odd members, and n_i+1 = (3n_i + 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

$\Vert L\Vert =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, n₁, n₂, …, n_i, m}. Then

$m=\frac{n^r}{2^k}{\displaystyle {\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 = 1¹0¹1²0³1¹, 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 ε < 10⁻¹⁸ such that

${\displaystyle {\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 = 2^k.

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 + ε)ⁿ 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 + ε)ⁿ 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 + ε)ⁿ is a non-integer for all integers n, leading to the desired result.

It follows that (3 + ε)^r ≠ 2^k 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\}$ , {n_i} the minimal extreme points and {m_i} the maximal extreme points. These numbers obey the basic inequalities m_i > n_i for each i ≥ 1. Furthermore, each n_i 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 {t_i} (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 m_i 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 m_i + 1 is divisible by 3^r and n_i + 1 is divisible by 2^r and for certain positive integers p₁ and p₂,

$m_i+1=3^r{p}^1$ and $n_i+1=2^r{p}^2$

But from (6.3), 2^r(3^rp₁) = 3^r(2^rp₂) and therefore p₁ = p₂ = t_i ≥ 1 for some unique t_i. 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 = 1²0³1³0²1⁴0¹1¹ written as L₁K₁L₂K₂L₃K₃L₄, where L₁ = 11, K₁ = 000, L₂ = 111, K₂ = 00, L₃ = 1111, K₃ = 0, and L₄ = 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 = 2²(49) − 1

440 = 3²(49) − 1

55 = 2³(7) − 1

188 = 3³(7) − 1

47 = 2⁴(3) − 1

242 = 3⁴(3) − 1

121 = 2¹(61) − 1

In this case, the pre-extremal sequence is {49, 7, 3, 61}.

We observe the following algorithm that generates the sequence {t_i} Since n_i 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 t_i since n_i + 1 = 2^vu or n_i = 2^vu − 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 t_i+1 in Terms of t₁

Theorem A leads to a formula for t_i+1 in terms of t₁. A preliminary result is needed first.

Theorem C. Let $L=1^{r_i}{0}^{s_i}$ and n_iLm_i. Then

$t_{i+1}=\frac{3^{r_i}{t}_i+2^{s_i}-1}{2^{r_i+s_i}}$ (9)

Proof: By hypothesis, n_iL_iK_im_i, 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 m_i is a generator of L_i+1 and n_i is a generator of L_i, 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\mathrm{...}{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}(2^{s_1}-1)$ .

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' = n₁ is an (odd) minimal extreme point of C, followed by an (even) maximal extreme point m₁, which is the resultant of r₁ odd members of C and generator of s₁ even members of C, followed by n₂, generator of r₂ odd members of C, ending with m₂, a maximal extreme point (even), the resultant of r₂ odd members of C. There are a total of r₁ + s₁ + r₂ = k members of C listed here (in other words a smaller Collatz sequence C', of which n₁ is a generator and m₂ the resultant). By (5)

$m_2=n_1{\left(3+\epsilon \right)}^r/2^k$

where r = r₁ + r₂. It will be convenient to let g = (3 + ε)^r − 3^r. 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(2^{s_1}-1)-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(2^{s_1}-1)-2^k=g(2^{r_1}-1)-3^r$

which can be put in the form

${\left(3+\epsilon \right)}^r{n}_1=2^{r_1}{3}^r(2^{s_1}-1)-2^k+3^r\left(n_1+1\right)$

Since n₁ 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, n₁ is not even so cannot contain 2 as a factor, so we have for some integer N'

${\left(3+\epsilon \right)}^r=2N^{\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.

References

[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