The Analysis of Convergence for the 3X + 1 Problem and Crandall Conjecture for the aX + 1 Problem

Zuojun Hu

Huadian Jinsha River Upstream Hydropower Development Co., Ltd., Chengdu, China.

DOI: 10.4236/apm.2021.115027                

Abstract

The 3X + 1 problem (Collatz conjecture) has been proposed for many years, however no major breakthrough has been made so far. As we know, the Crandall conjecture is a well-known generalization of the 3X + 1 problem. It is worth noting that, both conjectures are infamous for their simplicity in stating but intractability in solving. In this paper, I aim to provide a clear explanation about the reason why these two problems are difficult to handle and have very different characteristics on convergence of the series via creatively applying the probability theory and global expectancy value E(n) of energy contraction index. The corresponding convergence analysis explicitly shows that a = 3 leads to a difficult problem, while a > 3 leads to a divergent series. To the best of my knowledge, this is the first work to point out the difference between these cases. The corresponding results not only propose a new angle to analyze the 3X + 1 problem, but also shed some light on the future research.

Keywords

3X + 1 Problem, Crandall Conjecture, Energy Method, Expectancy Theory

1. Introduction

The 3X + 1 problem is known as the Collatz problem. It focuses on the behavior of the iteration of the function which takes odd integers n to 3n + 1 and even integers n to n/2. The Collatz conjecture declares that no matter starting from any positive integer n, if we repeat the iteration of this function, eventually we will converge to the value 1.

Its corresponding mathematical statement is as follows.

If S(X) is equal to 3X + 1 (X is a positive odd number) or X/2ⁿ (X is a positive even number, n is an unidentified value), starting from any positive integer X, iterating the function repeatedly to get a sequence of $S^{\left(0\right)}\left(X\right),S^{\left(1\right)}\left(X\right),S^{\left(2\right)}\left(X\right),\cdots$, where $S^{\left(0\right)}\left(X\right)=X$, $S^{\left(n+1\right)}\left(X\right)=S\left(S^{\left(n\right)}\left(X\right)\right)$ ( $n=0,1,2,\cdots$ ), there is a positive integer I, which makes $S^{\left(i\right)}\left(X\right)=\text{1}$ [1].

This problem is traditionally proposed by Lothar Collatz during his student days in the 1930’s. At that time, he was interested in graph theory and studied the behavior of iterations of mummer-theoretic functions as directed graphs. Although Collatz never published his iteration problems, he presented them at the International Congress of Mathematicians in 1950 in Cambridge. Then the original 3X + 1 problem appeared in print [2] [3] [4]. After that, the 3X + 1 problem has appeared in various forms. It is one of the most infamous unsolved puzzles in the word. Prizes have been offered for its solution for more than forty years, but no one has completely and successfully solved it [5].

1.1. Selecting a Template 3X + 1 Problem the Specified Calculation and Verification

1.1.1. The Specified Calculations

The 3X + 1 problem has been numerically checked for a large range of values on n.

In 1992, Leavens and Vermeulen proved that the conjecture is true for positive integers less than 5.6 × 10¹³.

In 2006, Distributed computing has proved for positive integers less than 510 × 10¹⁵.

Yoneda, the University of Tokyo (Japan) has proved that the conjecture is true for positive integers less than 2⁴⁰ ≈ 1.1 × 10¹² [6].

Fraenkel has check that all positive integers less than 2⁵⁰ have a finite stopping time and the conjecture is still not erroneous [7].

All these numerical experiments verify the correctness of the conjecture in a very large range of positive integers. Hence, most of the mathematicians believe that the conjecture is true and aim to find a theoretic proof for the conjecture. It is worth pointing out that, due to the large development of computer and software, the upper bound of positive integers that has been verified to be true is keeping increasing very quickly nowadays.

1.1.2. Find the Upper Bound of S⁽ⁱ⁾(X)

In 1976, Terras proved that almost all positive integers n (in the sense of natural density), S(n) < n exists [8].

In 1979, Allouche proved that for any a > 0.869, almost all positive integers n (in the sense of natural density), S(n) < n^a exists [6].

In 1994, Korec proved that for any a > ln3/ln4 ≈ 0.7924, almost all positive integers n (in the sense of natural density), S(n) < n^a exists.

In 2019, Fields Prize winner Terence Chi-Shen Tao published his results on arXiv.org, attempted to prove that as long as {f(n)} is a sequence of real numbers that tends to be positive infinity, for almost all positive integers n (in the sense of logarithmic density), S(n) < f(n) exists. In his conclusion, f(n) could be a sequence that growing slowly, such as f(n) = lnlnlnln(n) [9].

All these works established certain skew random walks on cyclic groups at high frequencies and estimated the certain renew processes which interact with a union of triangles. Though these works provide the closest conclusions to the original conjecture, they still can’t get on the final peak.

1.2. Crandall Conjecture

The 3X + 1 problem also has various extensions, the most famous extension is the aX + b problem proposed by Crandall in 1978. Generally, let a and b positive integers, a > 1, and b is odd integer, this so-called aX + b problem is specified as whether 1 can be obtained after a finite number of iterations for any positive odd number x?

It is obvious that a = 3, b = 1 is the 3X + 1 problem. After research, Crandall proposed the following conjecture: for all the other positive integers (a > 1), we can find a positive odd number r, which makes S⁽ⁱ⁾(r) is not equal to 1 for all positive integers except a = 3, b = 1 (3x + 1 problem).

Crandall proved that if b > 1, the conjecture is correct. In the case of aX + 1, he only proves that the conjecture is correct when a = 5, 181 and 1093 [10].

In 1995, Franco and Pom-erance proved that the Crandall conjecture about the aX + 1 problem is correct for almost all positive odd numbers a > 3, under the definition of asymptotic density.

However, both of the 3X + 1 problem and Crandall conjecture have not been solved yet. And to the best of my knowledge, the convergence analysis of these two problems is still blank.

1.3. Probabilistic Argument

Instead of directly solving the 3X + 1 problem, many researchers also proposed some heuristic probabilistic arguments to support the conjecture. For example, Olliveira and Silva proposed an empirical verification of the conjecture [11]; Sinai extends the 3X + 1 problem to a statistical (3X + 1) problem and studied its properties [12]; Thomas showed a non-uniform distribution property of most orbits [13]; Tao recently claimed that almost all orbits of the Collatz map attain almost bounded values [9]. Note that, these probabilistic approaches not only extend the original problem, but also provide some new ideas to the future study of the problem.

2. Energy Method, Expectancy Theory, Weak 3X + 1 Problem and Crandall Conjecture

In order to solve the 3X + 1 problem and the Crandall conjecture for the aX + 1 problem, the key is to prove that the global convergence (diffusion) of the iteration on the corresponding number field is consistent with the individual convergence (diffusion) and global convergence (diffusion) of the number field.

Some researchers have pointed out that, it is necessary to prove the uniqueness of the “4-1” cycle in the 3X + 1 loop. Otherwise, it is definite as the weak 3X + 1 problem which omits the loop factor [14] [15] [16].

Expected Value of Energy Contraction Index

For each iteration of an arbitrary positive odd number X, based on the description of the problem, the constructor $T\left(X\right)=\left(3X+1\right)/2^n$ (X is 1, 3, 5, … and n is an undefined value). By using the energy analysis method, defined 3 and 1 on the molecule as the expansion energy factor X, 2ⁿ on the denominator as the average contraction energy factor, when the contraction energy is greater than the expansion energy, the T(X) converges, so as expected value E(n) of energy contraction index, the larger the relative expansion energy, the faster speed of the convergence rate T(X) [16]. Now, I use some numerical instances to explicitly illustrate how to calculate E(n).

For example:

X = 7, based on the description of the problem, 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. There are 16 steps for 7 to converge to 1. The calculation of $E\left(n\right)=1\times 2/5+2\times 1/5+3\times 1/5+4\times 1/5=11/5=2.2$

X = 11, based on the description of the problem, 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. There are 14 steps for 11 to converge to 1.The calculation of $E\left(n\right)=1\times 1/4+2\times 1/4+3\times 1/4+4\times 1/4=10/4=2.25$

X = 27, based on the description of the problem, 27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. There are 111 steps for 27 to converge to 1. The calculation of $E\left(n\right)=1\times 24/41+2\times 10/41+3\times 3/41+4\times 3/41+5\times 1/41=70/41\approx 1.71$

Since 2^ln(3)/ln(2) = 3, 1.71 is larger than the energy equilibrium point ≈ ln(3)/ln(2) ≈ 1.585, compared with the above two equations, it is closer to the equilibrium point. Although the initial values are different, the relative speed of convergence to 1 is slower.

From these numerical examples we can clearly see that when n is sufficiently large and the corresponding X is sufficiently large too, the contribution of 1 on the molecule to the energy expansion is negligible, which can be regarded as an even transformation factor. So whether T’(X) = 3X/2ⁿ, X converges or not depends on the expansion-contraction ratio coefficient λ, that is 3/2ⁿ. Since the contraction energy index n is an undefined value, its global expected value E(n) is determined by the distribution of two factors in the even number of 3X + 1 (X is an odd positive integer).

By using the law of distribution, I state the above result as the following theory.

Theorem 2.1 The mathematically expected expression for the 2-factor distribution of 3X 1-type even numbers (x is positive odd) is $2-\left(2+n\right)/2^n$

Proof $S\left(X\right)=3X+1$, X is an odd positive number, which makes $X=2K+1$ ( $K=0,1,2,\cdots$ )

1) $S\left(X\right)=3X+1=3\left(2K+1\right)+1=6K+4=2\left(3K+2\right)$

That is 3X + 1 even number (X is an odd positive number) has at least one factor of 2.

2) $S\left(K\right)=2\left(3K+2\right)$ ( $K=0,1,2,\cdots$ )

$K=2K_1$ (50%) or $2K_1+1$ (50%)

Let $K=2K_1$

$S\left(K_1\right)=2\left(3\times 2K_1+2\right)=2\left(6K_1+2\right)=2^2\left(3K_1+1\right)$

That is the even number of 3X + 1 (X is an odd positive number) has at least two factors of 2 in proportion of 50% (That’s 1/2), and the remaining 50% (That’s 1/2) has only one factor of 2.

3) $S\left(K_1\right)=2^2\left(3K_1+1\right)$

$K_1=2K_2$ (50%) or $\text{2}{K}_{\text{2}}+\text{1}$ (50%)

Let $K_{\text{1}}=\text{2}{K}_{\text{2}}+\text{1}$

$S\left(K_2\right)=2^2\left[3\left(2K_2+1\right)+1\right]=2^2\left(6K_2+4\right)=2^3\left(3K_2+2\right)$

That is the even number of 3X + 1 (X is positive odd) has at least three factors of 2 in proportion of 25% (That’s 1/4), and the remaining 25% (That’s 1/4) has only two factors of 2.

4) If $S\left(K_n\right)=2^{n+1}\left(3K_n+2\right)$ (n is an even positive number)

So $S\left(K_{n+1}\right)$ is $K_n=2K_{n+1}+1$ (50%)

$S\left(K_n{}_{+1}\right)=2^{n+1}\left(3\times 2K_{n+1}+2\right)=2^{n+2}\left(3K_{n+1}+1\right)$

If $S\left(K_n\right)=2^{n+1}\left(3K_n+1\right)$ (n is an odd positive number)

So $S\left(K_{n+1}\right)$ is $K_n=2K_{n+1}+1$ (50%)

$S\left(K_{n+1}\right)=2^{n+1}\left[3\left(2K_{n+1}+1\right)+1\right]=2^{n+1}\left(6K_{n+1}+4\right)=2^{n+2}\left(3K_{n+1}+2\right)$

That is to say, the factor ratio of 3X + 1 even number (X is an odd positive number) with at least 2ⁿ⁺² of 2 in the proportion of (1/2)ⁿ⁺¹, and the remaining (1/2)ⁿ⁺¹ has only 2ⁿ⁺¹ factors of 2.

Therefore, in the even number of 3X + 1 type (X is an odd positive number), only one factor of 2 accounts for 1/2, only two factors of 2 account for 1/4, only three factors of 2 account for 1/8. Only n factors of 2 account for (1/2)ⁿ.

The mathematical expectation expression of its 2-factor distribution:

$E\left(n\right)=1\times 1/2+2\times 1/4+3\times 1/8+\cdots +n\times {\left(1/2\right)}^n$ (2.1)

$2\times E\left(n\right)=1\times 1+2\times 1/2+3\times 1/4+\cdots +n\times {\left(1/2\right)}^{n-1}$ (2.2)

Equation (2.2) minus Equation (2.1)

$E\left(n\right)=1\times 1/2+1/4+\cdots +{\left(1/2\right)}^{n-1}-n\times {\left(1/2\right)}^n$

$E\left(n\right)=2-2\times {\left(1/2\right)}^n-n\times {\left(1/2\right)}^n=2-\left(2+n\right)/2^n$ (2.3)

Theorem 2.2 When n tends to infinity, From Equation (2.3), the global expectancy value E(n) = 2, that is $T^{\prime }\left(X\right)=\lambda X=\left(3/2^{E\left(n\right)}\right)X=\left(3/4\right)X$, $\lambda =3/4<1$, $T^{\prime }\left(X\right)$ converges globally. In the same way, this distribution law is applicable to 5X + 1, 7X + 1, 9X + 1, the even number of type A (X is a positive odd number greater than 3) proves its global divergence.

Proof $S\left(X\right)=NX+\text{1}$, N and X are both odd positive numbers, which make $X=\text{2}K+\text{1}$ ( $K=0,1,2,\cdots$ )

1) $S\left(X\right)=NX+1=N\left(2K+1\right)+1=2NK+N+1=2\left[NK+\left(N+1\right)/2\right]$

Since N and X are both odd positive number, NX + 1 is an even number and has at least one factor of 2.

2) $S\left(K\right)=2\left[NK+\left(N+1\right)/2\right]$ ( $K=0,1,2,\cdots$ )

$K=2K_1$ (50%) or $2K_1+1$ (50%)

If $\left(N+1\right)/2$ is a positive even number, let $K=2K_1$

$S\left(K_1\right)=2^2\left[N{K}_1+\left(N+1\right)/4\right]$

If $\left(N+1\right)/2$ is a positive odd number, let $K=2K_1+1$

$S\left(K_1\right)=2^2\left[N{K}_1+\left(3N+1\right)/4\right]$

That is the even number of NX + 1 (N and X are both odd positive number) has at least two factors of 2 in proportion of 50% (That’s 1/2), and the remaining 50% (That’s 1/2) has only one factor of 2.

3) If $S\left(K_n\right)=2^{n+1}\left[N{K}_n+Z_1\right]$ (N is a positive odd number, Z₁ is a positive even number)

Then $S\left(K_{n+1}\right)$ is when $K_n=2K_{n+1}$ (50%)

$S\left(K_{n+1}\right)=2^{n+2}\left[N{K}_{n+1}+Z_1/2\right]$

If $S\left(K_n\right)=2^{n+1}\left[N{K}_n+Z_2\right]$ (N and Z₂ are both odd positive number)

Then $S\left(K_{n+1}\right)$ is when $K_n=2K_{n+1}$ (50%)

$S\left(K_{n+1}\right)=2^{n+1}\left[N\left(2K_{n+1}+1\right)+Z_2\right]=2^{n+2}\left[N{K}_{n+1}+\left(N+Z_2\right)/2\right]$

That is to say, the factor ratio of NX + 1 even number (N and X are both odd positive number) with at least 2n + 2 of 2 in the proportion of (1/2)ⁿ⁺¹, and the remaining (1/2)ⁿ⁺¹ has only 2n + 1 factors of 2.

Therefore, in the even number of NX + 1 type (N and X are both odd positive number), only one factor of 2 accounts for 1/2, only two factors of 2 account for 1/4, only three factors of 2 account for 1/8. Only n factors of 2 account for (1/2)ⁿ. The mathematical expectation expression of the 2-factor distribution is the same as Equation (2.3), That is $E\left(n\right)=1\times 1/2+2\times 1/4+3\times 1/8+\cdots +n\times {\left(1/2\right)}^n=2-\left(2+n\right)/2^n$

The above proof and theorem 2.2 can lead to the following important result:

The global expected value E(N) of 2-factor distribution is always 2.

On the other hand, if the following conditions are met:

1) After infinite iterations, it approaches infinity;

2) Loops do not occur during iterations.

X_i will finally diverge (calculation verification shows that the smaller number converges to 1) with a sufficiently large positive integer.

Theorem 2.3 Since in the infinite acyclic iteration, the even number of 3X + 1 type of the large number X_i is infinite and does not repeat, According to the law of large numbers, the local expected value of the contraction energy index must get close to the global expected value 2, and the expansion-contraction ratio coefficient λ is less than 1, X_i convergences , so the assumption is not true, and the individual convergence is consistent with the global convergence, that is, In a statistical sense, the weak 3X + 1 problem established.

For the Crandall conjecture of the ax + 1 problem, $\lambda =5/4,7/4,9/4,\cdots >1$, In the same way, it can prove that it spreads at 5X + 1, 7X + 1, 9X + 1, …. The S⁽ⁱ⁾(r) is always not 1 when the even number of type (X is a positive odd number greater than 3) does not intersect singularity 2ⁿ.

3. Conclusions

This article analyzes the convergence for the 3X + 1 problem and Crandall conjecture. It creatively applies the global expectance value E(n) of energy contraction index, and proposes a new angle to check the function iteration process. Moreover, it establishes a relationship between sequence process analysis and static mean via probability and statistics.

The corresponding analysis clearly shows the orbit of iterations on the 3X + 1 problem is on the imbalanced point, hence it is difficult to depict the orbit. Besides, this analysis also shows the reason why (a > 3) leads to a divergent series.

It is worth pointing out that, this manuscript is the first work to point out the difference between these cases by creatively applying the probability analysis and global expectancy value E(n) of energy contraction index. Since a lot of researchers have tried various ways to approach the 3X + 1 problem but it has not been solved yet for many years, this manuscript indeed provides a totally new idea to address the problem. Hence, it may play a substantial role in the future study and shed some light on the research of this area.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Lagarias, J. (1985) The 3x+1 Problem and Its Generalizations. The American Mathematical Monthly, 92, 3-23. https://doi.org/10.1080/00029890.1985.11971528
[2]	Atkin, A. (1966) Comment on Problem 63-13. SIAM Review, 8, 234-236. https://doi.org/10.1137/1008050
[3]	Klamkin, A. (1963) Problem 63-12. SIAM Review, 5, 275-276. https://doi.org/10.1137/1005074
[4]	Shanks, D. (1965) Comments on Problem 63-13. SIAM Review, 7, 284-286. https://doi.org/10.1137/1007049
[5]	Williams, C., Thwaaites, B., van der Poorten, A., Edwards, W. and Williams, L. (1982) Ulam’s Conjecture Continued Again, 1000 Pounds for Proof. PPC Calculator Journal, 9, 23-24.
[6]	Allouche, J. (1979) Sur la conjecture de “Syracuse-Kakutani-Collatz”. Seminaire de Théorie des Nombres de Bordeaux 8 (1978-1979), 1-16.
[7]	Fraenkel, A. (1981) Private Communication.
[8]	Terras, R. (1979) A Stopping Time Problem on the Positive Integers. Acta Arithmetica, 30, 241-252. https://doi.org/10.4064/aa-30-3-241-252
[9]	Tao, T. (2020) Almost All Orbits of the Collatz Map Attain Almost Bounded Values. https://arxiv.org/abs/1909.03562
[10]	Crandall, R. (1978) On the “3x+1” Problem. Mathematics of Computation, 32, 1281-1292. https://doi.org/10.2307/2006353
[11]	Oliveira, T. and Silva, E. (2010) Empirical Verification of the 3X+1 and Related Conjectures, the Ultimate Challenge: The 3X+1 Problem, 189207. American Mathematical Society, Providence.
[12]	Sinai, Y. (2003) Statistical (3X+1) Problem. Communications on Pure and Applied Mathematics, 56, 1016-1028. https://doi.org/10.1002/cpa.10084
[13]	Thomas, A. (2017) A Non-Uniform Distribution Property of Most Orbits, in Case the 3X+1 Conjecture Is True. Acta Arithmetica, 178, 125-134. https://doi.org/10.4064/aa8385-9-2016
[14]	Lagarias, J. (1990) The Set of Rational Cycles for the 3x+1 Problem. Acta Arithmetica, 56, 33-53. https://doi.org/10.4064/aa-56-1-33-53
[15]	Lagarias, J. and Weiss, A. (1992) The 3x+1 Problem: Two Stochastic of Rational Models. Annals of Applied Probability, 2, 229-261. https://doi.org/10.1214/aoap/1177005779
[16]	Zhou, S., Xie, S. and Pan, C. (2006) Probability Theory and Mathematical Statistics. 3rd Edition, Higher Education Press, Beijing.