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

Show more

1. Introduction

The 3*X* + 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 3*n* + 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 3*X* + 1 (*X* is a positive odd number) or *X*/2^{n} (*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 3*X* + 1 problem appeared in print [2] [3] [4]. After that, the 3*X* + 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 3*X* + 1 Problem the Specified Calculation and Verification

1.1.1. The Specified Calculations

The 3*X* + 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^{13}.

In 2006, Distributed computing has proved for positive integers less than 510 × 10^{15}.

Yoneda, the University of Tokyo (Japan) has proved that the conjecture is true for positive integers less than 2^{40} ≈ 1.1 × 10^{12} [6].

Fraenkel has check that all positive integers less than 2^{50} 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*^{(i)}(*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 3*X* + 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 3*X* + 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*^{(i)}(*r*) is not equal to 1 for all positive integers except *a* = 3, *b* = 1 (3*x* + 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 3*X* + 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 3*X* + 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 3*X* + 1 problem to a statistical (3*X* + 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 3*X* + 1 Problem and Crandall Conjecture

In order to solve the 3*X* + 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 3*X* + 1 loop. Otherwise, it is definite as the weak 3*X* + 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* ^{n}* on the denominator as the average contraction energy factor, when the contraction energy is greater than the expansion energy, the

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*) = 3*X*/2* ^{n}*,

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 3*X* 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 3*X* + 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=2{K}_{1}$ (50%) or $2{K}_{1}+1$ (50%)

Let $K=2{K}_{1}$

$S\left({K}_{1}\right)=2\left(3\times 2{K}_{1}+2\right)=2\left(6{K}_{1}+2\right)={2}^{2}\left(3{K}_{1}+1\right)$

That is the even number of 3*X* + 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(3{K}_{1}+1\right)$

${K}_{1}=2{K}_{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(2{K}_{2}+1\right)+1\right]={2}^{2}\left(6{K}_{2}+4\right)={2}^{3}\left(3{K}_{2}+2\right)$

That is the even number of 3*X* + 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(3{K}_{n}+2\right)$ (*n* is an even positive number)

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

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

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

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

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

That is to say, the factor ratio of 3*X* + 1 even number (*X* is an odd positive number) with at least 2^{n}^{+2} of 2 in the proportion of (1/2)^{n}^{+1}, and the remaining (1/2)^{n}^{+1} has only 2^{n}^{+1} factors of 2.

Therefore, in the even number of 3*X* + 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)* ^{n}*.

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 5*X* + 1, 7*X* + 1, 9*X* + 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=2{K}_{1}$ (50%) or $2{K}_{1}+1$ (50%)

If $\left(N+1\right)/2$ is a positive even number, let $K=2{K}_{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=2{K}_{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*_{1} is a positive even number)

Then $S\left({K}_{n+1}\right)$ is when ${K}_{n}=2{K}_{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*_{2} are both odd positive number)

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

$S\left({K}_{n+1}\right)={2}^{n+1}\left[N\left(2{K}_{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 2*n* + 2 of 2 in the proportion of (1/2)^{n}^{+1}, and the remaining (1/2)^{n}^{+1} has only 2*n* + 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)* ^{n}*. 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 3*X* + 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

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 5*X* + 1, 7*X* + 1, 9*X* + 1, …. The *S*^{(}^{i}^{)}(*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* ^{n}*.

3. Conclusions

This article analyzes the convergence for the 3*X* + 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 3*X* + 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 3*X* + 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.

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.