A Solution to the 3x + 1 Problem ()

David C. Kay^{}

Weaverville, NC, USA.

**DOI: **10.4236/ajcm.2023.132020
PDF
HTML XML
92
Downloads
520
Views
Citations

Weaverville, NC, USA.

The author makes the claim to have a solution for the famous 3*x* + 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 3*x* + 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 (3*n* + 1)/2 if *n* is odd.

Solving the 3*x* + 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 3*x* + 1 conjecture has been verified by special computer programs for all positive integers up to *n** = 20 × 2^{58} = 5.8 × 10^{18} (more recently to *n** = 8.7 × 10^{18}).

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

As in [1] , we refer to *n _{i}* as the pre-resultant of a finite Collatz sequence

$\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*_{1}, *n*_{2}, …, *n _{i}*,

$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^{1}0^{1}1^{2}0^{3}1^{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

${\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

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

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 +

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

It follows that (3 + *ε*)* ^{r}* ≠ 2

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 {

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

${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

${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

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

But from (6.3), 2* ^{r}*(3

${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^{2}0^{3}1^{3}0^{2}1^{4}0^{1}1^{1} written as *L*_{1}*K*_{1}*L*_{2}*K*_{2}*L*_{3}*K*_{3}*L*_{4}, where *L*_{1} = 11, *K*_{1} = 000, *L*_{2} = 111, *K*_{2} = 00, *L*_{3} = 1111, *K*_{3} = 0, and *L*_{4} = 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^{2}(49) − 1

440 = 3^{2}(49) − 1

55 = 2^{3}(7) − 1

188 = 3^{3}(7) − 1

47 = 2^{4}(3) − 1

242 = 3^{4}(3) − 1

121 = 2^{1}(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

Theorem B. The pre-extremal sequence consists of all odd integers.

7. A Formula for *t _{i}*

Theorem A leads to a formula for *t _{i}*

Theorem C. Let
$L={1}^{{r}_{i}}{0}^{{s}_{i}}$ and *n _{i}Lm_{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 _{i}L_{i}K_{i}m_{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

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

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

where *r* = *r*_{1} + *r*_{2}. It will be convenient to let *g* = (3 + *ε*)* ^{r}* − 3

${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*_{1} 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*_{1} 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 3*x* + 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 |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.