The 3x + 1 Conjecture, a Direct Path

Salvador Bermúdez Gómez

Instituto Politécnico Nacional, SEPI-ESIME-Zacatenco, Mexico City, México.

DOI: 10.4236/ajcm.2023.132018                

Abstract

The 3x + 1 problem, is a math problem that has baffled mathematicians for over 50 years. It’s easy to explain: take any positive number, if it’s even, divide it by 2; if it’s odd, multiply it by 3 and add 1. Repeat this process with the resulting number, and the conjecture says that you will eventually reach 1. Despite testing all starting values up to an enormous number, no one has proved the conjecture is true for all possible starting values. The problem’s importance lies in its simplicity and difficulty, inspiring new ideas in mathematics and advancing fields like number theory, dynamical systems, and computer science. Proving or disproving the conjecture would revolutionize our understanding of math. The presence of infinite sequences is a matter of question. To investigate and solve this conjecture, we are utilizing a novel approach involving the fields of number theory and computer science.

Keywords

3x + 1, Collatz, Solved, Computer Science, Number Theory, New Algo-rithm

1. The 3x + 1 Problem and Main Conjecture

The 3x + 1 problem or Collatz Conjecture, also known as the 3n + 1 problem, is a famous unsolved problem in mathematics that has puzzled mathematicians for over half a century. The problem is deceptively simple to state, but it has resisted all attempts to solve it.

The conjecture is defined as follows: take any positive integer n. If n is even, divide it by 2; if n is odd, multiply it by 3 and add 1. Continue this process with the resulting number, and repeat indefinitely. The conjecture states that no matter what number you start with, this process will eventually reach the number 1. The Recursive Algorithm is the next:

$f_c\left(n\right)=(\begin{array}{ll}3n+1\hfill & \text{if}n\text{is}\text{odd}\hfill \\ \frac{n}{2}\hfill & \text{if}n\text{is}\text{even}\hfill \\ stop\hfill & \text{if}n\text{is}\text{1}\hfill \end{array}$ (1)

For example, if you start with the number 6, the sequence will be: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

The Collatz Conjecture has been verified by computer calculations for all starting values up to 2⁶⁸ [1] , which is an enormous number. However, despite this evidence, no one has been able to prove that the conjecture is true for all possible starting values.

The importance of the Collatz Conjecture lies in its simplicity and ubiquity. It is easy to understand and explain, yet it remains one of the most challenging problems in mathematics. It is a problem that has inspired mathematicians to develop new techniques and ideas, and has led to advances in fields as diverse as number theory, dynamical systems, and computer science.

Moreover, if the conjecture is proved to be true, it would have significant implications for our understanding of number theory and the behavior of mathematical systems. On the other hand, if it is proved to be false, it would revolutionize our understanding of number theory, and the nature of mathematical proofs. Then, the main problem of the 3x + 1 function consists of knowing if all sequences that are obtained by having applied this function recursively, lead irremediably to the value 1.

In summary, the Collatz Conjecture is a fascinating and important problem in mathematics that has eluded solution for over half a century. Its simplicity, ubiquity, and potential implications make it a highly motivating problem to solve for mathematicians, and its resolution would have a significant impact on our understanding of number theory and mathematical systems.

The central issue with the 3x + 1 function is determining if all sequences produced through its recursive application will ultimately converge to the value 1. Additionally, there is a question of whether a special sequence, referred to as the Q sequence, exists that never ends. In this paper, a formal proof is presented that the existence of an infinite sequence generated by the function is not possible. Despite the straightforward nature of the 3x + 1 function, its complexity is quite intricate [2] . There are multiple proofs that examine various approaches [3] [4] [5] [6] [7] , including [8] , which explore different paths [9] [10] . The proof presented here is both simple and insightful, adhering to principles of number theory and computer science and divided into three stages.

The first stage involves finding the form of the supposed infinite Q sequence by assuming its existence. It is assumed, by contradiction, that the Q sequence exists and never reaches 1. This Q sequence must have the pattern E-O-E-O… (EVEN-ODD-EVEN-ODD…) repeating indefinitely, under the function $f_c$ . The second stage shows that this form is impossible to obtain, since any sequence under the function $f_c$ , presents the pattern E-E.

The third stage establishes the contradiction and proves that the Q sequence cannot exist. The proof systematically answers Lagarias’ question [11] by finding the form and characteristics of the hypothetical infinite Q sequence.

2. The Proof

Theorem 1. Every sequence of the 3x + 1 algorithm, reaches 1 (Main conjecture¹)

Proof. To prove it by contradiction, that is, it is assumed true that there is a sequence that DOES NOT REACH 1, which we will call Q.

Let Q be the infinite sequence that does not reach 1, therefore $1\notin Q$ and $Q=Q_1,Q_2,Q_3,\cdots ,\infty$ , where $f_c\left(Q_1\right)=Q_2$ , $f_c\left(Q_2\right)=Q_3$ , $\cdots$ .

Let’s ask the next question, which is the form of this Q sequence in terms of odd and even numbers?

This is done to observe what is the correspondence between the even and odd numbers in the Q sequence. To know this pattern, one sorts the Q sequence, by ascending order, which is supported by the Axiom of choice [12] [13] , such that Q’ is Q sorted. Then one makes two ordered sequences, one of the even numbers $Q_E=E_1,E_2,\cdots$ and the other from odd numbers $Q_O=O_1,O_2,\cdots$ Getting to the first pattern $\boxed{R_1^{\ast })E_i<E_{i+1},O_i<O_{i+1}}$ .

It follows that $E_1$ is the smallest even number, and $O_1$ , is the smallest odd number of the sequence. As illustrated in Figure 1. Therefore $Q^{\prime }=Q_O\cup Q_E$ .

We process $Q^{\prime }$ by the function $f_c$ , in this case, Obviously, $f_c\left(E_1\right)=O_1$ , otherwise if $f_c\left(E_1\right)=O_x$ ; for some $x>1$ , for example, $O_2\mathrm{,}{O}_3,\cdots$ then $O_x<O_1$ , which contradicts $R_1^{\ast }$ , since $E_1$ is the smallest even number, which will generate the smallest odd number. Now $f_c\left(E_2\right)=O_2$ , otherwise if $f_c\left(E_2\right)=O_x$ for some $x>2$ , for example, $O_3\mathrm{,}{O}_4,\cdots$ then $O_x<O_2$ , which contradicts $R_1^{\ast }$ , since $E_2$ is the smallest even number after $E_1$ , which will generate the smallest odd number after $O_1$ . The reasoning follows the same way for $E_3\mathrm{,}{E}_4,\cdots$

Next, we have $f_c\left(O_1\right)=E_2$ , otherwise if $f_c\left(O_1\right)=3\left(O_1\right)+1=2^r\left(O_y\right)$ , for some $r\ge 2$ , therefore $O_y<O_1$ contradicting $R_1^{\ast }$ , being $O_1$ the smallest odd number.

Figure 1. Odd and even numbers from Q Sequence are sorted.

Now $f_c\left(O_2\right)=E_3$ , otherwise if $f_c\left(O_2\right)=3\left(O_2\right)+1=2^r\left(O_y\right)$ , for some $r\ge 2$ , therefore $O_y<O_2$ contradicting $R_1^{\ast }$ , being $O_2$ the smallest odd number, after $O_1$ . The reasoning follows the same way for $O_3\mathrm{,}{O}_4\mathrm{,}\cdots$

It follows that the relationship between even and odd numbers in the $Q^{\prime }$ sequence, is presented as: $\boxed{R_2^{\ast })f_c\left(E_r\right)=O_r\mathrm{,}{f}_c\left(O_r\right)=E_{r+1}}$ , $r\in \mathbb{N}$ .

According to this, the $Q^{\prime }$ sequence follows the pattern E-O-E-O-E-O-… ∞. Therefore the $Q^{\prime }$ sequence cannot have 2 or more even numbers together.

If we have two sets with the same elements, we call them equal sets [14] , it does not matter what order the elements are in. What matters is that the sets have the same number of elements and that elements be equal in each set. Therefore Q and $Q^{\prime }$ are equivalent sets, and equal sets [12] .

We conclude that $Q^{\prime }=Q$ . Then $Q^{\prime }=\stackrel{⌢}{E_1,O_1},\stackrel{⌢}{E_2,O_2},\stackrel{⌢}{E_3,O_3},\cdots$ where there are no EVEN-EVEN numbers together(E-E) in the sequence.

Consequently $Q=\stackrel{⌢}{E_1,O_1},\stackrel{⌢}{E_2,O_2},\stackrel{⌢}{E_3,O_3},\cdots$ .

In summary this first stage

1) The form of $Q=\stackrel{⌢}{E_1,O_1},\stackrel{⌢}{E_2,O_2},\stackrel{⌢}{E_3,O_3},\cdots$ is EVEN-ODD…, alternating, forever.

2) Two even numbers cannot exist together in the infinite Q sequence.

In this second stage, we are going to prove that the pattern E-E occurs in all the sequences generated by the function $f_c\left(n\right)$ . To prove this.

Let any odd number be $O_x=2^{k}m-1$ ; $m=\text{odd}$ , $k\ge 1$ , $k,m\in \mathbb{N}$ , applying $f_c$ , after 2k iterations, we get the pattern E-E (Even-Even).

$2^k\cdot m-1$ (ODD)

$3\cdot 2^k\cdot m-2$ (EVEN)

$⋮$

$3^k\cdot 2^{k-k+1}\cdot m-2$ (EVEN)

$3^k\cdot m-1$ (EVEN)

A numerical example:

$2^4\cdot 5-1$ (ODD)

$3\cdot 2^4\cdot 5-2$ (EVEN)

$3\cdot 2^3\cdot 5-1$ (ODD)

$3^2\cdot 2^3\cdot 5-2$ (EVEN)

$3^2\cdot 2^2\cdot 5-1$ (ODD)

$3^3\cdot 2^2\cdot 5-2$ (EVEN)

$3^3\cdot 2^1\cdot 5-1$ (ODD)

$3^4\cdot 2^1\cdot 5-2$ (EVEN)

$3^4\cdot 5-1$ (EVEN)

The assumption of the existence of the Q sequence is contradicted when the E-O-E-O-E…pattern is disrupted by the presence of at least two consecutive even numbers (E-E…) in any sequence generated by $f_c$ .

Third Stage.

The pattern of the Q sequence is E-O-E-O…, which continues infinitely without reaching 1. Meanwhile, the function $f_c$ produces the pattern E-E. Therefore, it can be logically concluded that the Q sequence cannot be generated by the $f_c$ function.

In logical form: The infinite pattern of even and odd numbers E-O-E-O… is implied by the Q sequence, which does not converge to 1. On the other hand, the function $f_c$ produces the pattern E-E. Therefore, it is not possible for the fc function to generate the Q sequence.

The theorem has been proven.

3. Conclusion

The 3x + 1 conjecture is notable for its simple approach and complex solutions. One solution, proposed using the language of mathematics and computer science, involves sorting the Q sequence to reveal the relationships $R_1^{\ast }$ and $R_2^{\ast }$ . These relationships enforce a unique pattern in Q, characterized by the alternating sequence of even and odd numbers E-O-E-O…, and exclude other patterns, such as the presence of consecutive even numbers E-E. However, all functions generated by the $f_c$ function exhibit the pattern …E-E…, making it impossible for $f_c$ to produce the Q sequence. In conclusion, as mathematician Paul Erdös noted [15] , systematic mathematics has the potential to solve many complex problems.

NOTES

¹There are other conjectures, such as the existence of another cycles, in addition to cycle 4, 2, 1, which will not be discussed here.

Conflicts of Interest

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

References

[1]	Ren, W., Li, S.M., Xiao, R.Y. and Bi, W. (2018) Collatz Conjecture for 2ˆ 100000-1 Is True-Algorithms for Verifying Extremely Large Numbers. 2018 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/ IOP/SCI), Guangzhou, 8-12 October 2018, 411-416. https://doi.org/10.1109/SmartWorld.2018.00099
[2]	Lagarias, J.C. (2003) The 3x + 1 Problem: An Annotated Bibliography (1963-1999). https://doi.org/10.48550/arXiv.math/0309224
[3]	Belaga, E.G. and Mignotte, M. (1998) Embedding the 3x + 1 Conjecture in a 3x + d Context. Experimental Mathematics, 7, 145-151. https://doi.org/10.1080/10586458.1998.10504364
[4]	Applegate, D. and Lagarias, J. (2003) Lower Bounds for the Total Stopping Time of 3x + 1 Iterates. Mathematics of Computation, 72, 1035-1049. https://doi.org/10.1090/S0025-5718-02-01425-4
[5]	Lagarias, J.C. (2010) The Ultimate Challenge: The $3x + 1$ Problem. American Mathematical Society, Providence. https://doi.org/10.1090/mbk/078
[6]	Monks, K.M. (2006) The Sufficiency of Arithmetic Progressions for the 3x + 1 Conjecture. Proceedings of the American Mathematical Society, 134, 2861-2872. https://doi.org/10.1090/S0002-9939-06-08567-4
[7]	Krasikov, I. (1989) How Many Numbers Satisfy the 3x + 1 Conjecture? International Journal of Mathematics and Mathematical Sciences, 12, 791-796. https://doi.org/10.1155/S0161171289000979
[8]	Feinstein, C.A. (2004) The Collatz 3n + 1 Conjecture Is Unprovable. Science Direct Working Paper.
[9]	Mandadi, V. and Paramwswari, D. (2019) Verification of Collatz Conjecture: An Algorithmic Approach Based on Binary Representation of Integers. arXiv: 1912.05942.
[10]	Venkatesulu, M. and Parameswari, C.D. (2020) Verification of Collatz Conjecture: An Algorithmic Approach. WSEAS Transactions on Engineering World, 2, 71-75.
[11]	Lagarias, J.C. (1985) The 3x + 1 Problem and Its Generalizations. The American Mathematical Monthly, 92, 3-23. https://doi.org/10.1080/00029890.1985.11971528
[12]	Halmos, P.R. (2017) Naive Set Theory. Courier Dover Publications, New York.
[13]	Suppes, P. (1972) Axiomatic Set Theory. Courier Corporation, Chelmsford.
[14]	Burgess, J.P. (2022) Set Theory. Cambridge University Press, Cambridge.
[15]	Guy, R. (2004) Unsolved Problems in Number Theory. Springer Science & Business Media, Berlin. https://doi.org/10.1007/978-0-387-26677-0