Others

# Reduced Collatz Dynamics Data Reveals Properties for the Future Proof of Collatz Conjecture

Collatz conjecture is also known as 3x+1 conjecture. For verifying the conjecture, we design an algorithm that can output reduced dynamics (occurred 3*x+1 or x/2 computations from a starting integer to the first integer smaller than the starting integer) and original dynamics of integers (from a starting integer to 1). Especially, the starting integer has no upper bound. That is, extremely large integers with length of about 100000 bits, e.g., 2^{100000}-1, can be verified for Collatz conjecture, which is much larger than current upper bound (about 2^{60}). We analyze the properties of those data (e.g., reduced dynamics) and discover the following laws: reduced dynamics is periodic and the period is the length of its reduced dynamics; the count of x/2 equals to minimal integer that is not less than the count of (3*x+1)/2 times ln(1.5)/ln(2). Besides, we observe that all integers are partitioned regularly in half and half iteratively along with the prolonging of reduced dynamics, thus given a reduced dynamics, we can compute a residue class that presents this reduced dynamics by a proposed algorithm. It creates an one-to-one mapping between a reduced dynamics and a residue class. Those observations from data can reveal the properties of reduced dynamics, which are proved mathematically in our other papers (see references). If it can be proved that every integer has reduced dynamics, then every integer will have original dynamics (i.e., Collatz conjecture will be true). The data set includes reduced dynamics of all odd positive integers in [3, 99999999] whose remainder is 3 when dividing 4, original dynamics of some extremely large integers, and all computer source codes in C that implement our proposed algorithms for generating data (i.e., reduced or original dynamics).

The Collatz conjecture is a mathematical conjecture that is first proposed by Lothar Collatz in 1937. Collatz conjecture is also known as 3x+1 problem, which states simply as follows: Take any positive integer number x. If x is even, divide it by 2 to get x/2. If x is odd, multiply it by 3 and add 1 to get 3*x + 1. Repeat the process again and again. The Collatz conjecture is that no matter what the starting number (i.e., x) is taken, the process will always eventually reach 1.

Original dynamics is from starting number to 1. In contrast, reduced dynamics is from starting number to the first number that is less than the starting number. We propose to study reduced dynamics , because it is more primitive - it is the component (building block) of original dynamics.  Indeed, reduced dynamics presents inner regulations such as period that does not exist in original dynamics. We find that 3*x+1 is always even and is always followed by x/2. Thus, 3*x+1 and x/2 can be combined together as (3*x+1)/2. Because the computation for Collatz conjecture is either (3*x+1)/2 or x/2, we use “I” to denote (3*x+1)/2 and “O” to denote x/2. Intuitively, if all positive integers can return to an integer that smaller than it, then it will finally return 1. Indeed, we propose the reduced Collatz conjecture and prove it is equivalent to Collatz conjecture formally in another paper . We can prove that if reduced dynamics for all positive integers exist, then original dynamics for all positive integers exist. Inverse direction is also guaranteed. Here, we assume reduced dynamics for 1 is (3*x+1)/2 and x/2, i.e., “IO”.

Reduced dynamics for some integers are trivial. For example, reduced dynamics for even integer is “O”, as after x/2 the transformed number is less than the starting number. Besides, reduced dynamics for odd with form 4k+1 is “IO”. It can be proved as follows: Suppose starting integer is x, and x is 4k+1 (k is a natural number). Thus, (3*x+1)/2 occurs. After (3*x+1)/2, x is (12k+3+1)/2, which is 6k+2. Thus, x/2 occurs. After x/2, transformed number is 3k+1, which is less than 4k+1. Thus, reduced dynamics is obtained and is “IO”. Furthermore, for including special case when x equals 1, we intentionally assume the reduced dynamics for 1 is “IO”. In the following, we only concentrate on reduced dynamics for odd with 4k+3.

To prove the reduced Collatz conjecture, i.e., to prove all positive integers has reduced dynamics, we study the properties in reduced dynamics. We design a computer program that can output reduced dynamics for odd integers with 4k+3, e.g, [3-99999999]. Outputting (reduced) dynamics for much larger integers are also possible. The source code in C is txpo9.c. There are 5 options in arguments for more flexible output. Those data can reveal the properties of reduced dynamics. The most important are ratio and period. We discover the ratio - the count of x/2 over the count of (3*x+1)/2 - is bounded by a constant value, ln(1.5)/ln(2). We prove mathematically that the ratio of reduced dynamics is larger than lambda = ln(1.5)/ln(2)  0.58496250 formally in another paper . Those data outputted by txpo9.c can be used to verify this bound. The data shows that our analysis on the bound of ratio is right. Indeed, we can give the equation on the count of x/2 and the count of (3*x+1)/2 for any reduced dynamics. That is, CntO(c) = ceil(CntI(c)*lambda), and c is any reduced dynamics in terms of “I” and “O” with length larger than 1. Here, CntO(c) is a function returns the count of “O” in inputting string denoted as c, and CntI(c) is a function returns the count of “I” in inputting string denoted as c. For example, “O” is a reduced dynamics for even, it is trivial and listed aside. “IO” is reduced dyancmics for odd with 4k+1, we can check the equation as follows:

CntO(IO)=1, CntI(IO)=1, CntO(c)=1,

ceil(CntI(c)*lambda)) = ceil(1*lambda)=ceil(1*ln(1.5)/ln(2))=ceil(0.58496250)=1.

It is worth to note that - the bound can help us generate all valid reduced dynamics by algorithm, instead of selecting a positive number to compute its reduced dynamics. Besides, we also discover that the period of reduced dynamics exist. That is, if the reduced dynamics of x is a sequence consisting of “I” and “O” with length L, then the reduced dynamics of x+2L equals the reduced dynamics of x. We also prove it mathematically in another paper .  This period can also be observed and verified in the data file that is outputted by the program txpo9.c. Note that, for the better vision in computer program output, we use “-” to represent “I” (i.e., the computation of (3*x+1)/2) and “0” to represent “O” (i.e., the computation of x/2) .

Currently, the largest integer being verified for Collatz conjecture is about 260 [2,3]. To verify whether extremely large integers such as 2100000－1 can return 1, we design a new algorithm  to compute 3*x+1, which is O(lnx). This dedicated algorithm can change numerical computation into bit or Boolean computation, hence, original dynamics for extremely large integer without upper bound can be computed. By this algorithm, we thus design computer program that can output original dynamics for extremely large integers without upper-bound such as 2100000－1, which is the largest integer being verified until now. The source code in C is txpo15.c. The bit length of extremely large integer can be set up by “macro” (named MAXLEN) in source code. The program can output the original dynamics (called CODE) of a starting integer in terms of “-” presenting (3*x+1)/2 and “0” presenting x/2. This data can be used for verifying whether extremely large number can go to 1 finally. Note that, there is no upper bound for extremely large starting integer; all is a timing issue. We just use desktop PC (Intel Core i5-6500 3.2GHz) to compute the results for about 15 days.

After we study the ratio for reduced dynamics, we continue to study the ratio for original dynamics, especially for extremely large integers asymptotically. We design a computer program that can randomly generate extremely large integers and output their original dynamics. The source code is txpo10b.c. The bit length of integers can be defined by “macro” (named MAXLEN) in source code. The number of randomly generated integers can be set by inputting argument. The program can output the original dynamics of a starting integer in terms of “-” presenting (3*x+1)/2 and “0” presenting x/2. This data can be used for observing the relation between the count of “-” and the count of “0”. By analyzing outputting data, we discover that the ratio, which is the count of “-” over the count of “0”, is 1 asymptotically with the grow of starting integer.

We further study a reverse problem - given a reduced dynamics or partial dynamics, can we compute a residue class who presents that dynamics. We design a dedicated algorithm that takes as input a dynamics with length t consists of “I” or “O” can output a residue class who present this dynamics in the first t transformations. We thus design computer program that can output a reside class by inputting a reduced dynamics or partial dynamics. That is, inputting c{I,O}L, CntO(s) ≤ ceil(CntI(s)*lambda), lambda=ln(1.5)/ln(2)=0.58469250, s=Substr(c,1,i), i=1,2,., L,

where CntO(s) returns the count of “O” in string denoted as s; CntI(s) returns the count of “I” in string denoted as s; ceil(x) returns the minimal integer that is not less than x; Substr(c,1,i) returns the first i characters in terms of “I” or “O” (i.e., sub-string) in string denoted as c. In other words, the dynamics is above of or cutting ratio line in our proposed Collatz graph (e.g., Figure 2). Note that, the algorithm is quit lightweight and designed from our formal proof of Partition Theorem - We prove that all natural numbers are partitioned regularly corresponding to ongoing dynamics. Given any natural number x that equals i module 2t (i is an odd integer), the first t transformations in terms of “I” or “O” can be determined and identical with the first t transformations of of i. Once current value after t (t is greater or equal to 2) transformations of “I” or “O”, is less than x, then reduced dynamics of x is obtained. Otherwise, the residue class of x (namely, i module 2t) can be partitioned into two halves (namely, i module 2t+1 and i+2t module 2t+1), and either half presents “I” or “O” in intermediately forthcoming (t+1)-th transformation.

Dataset:

Wei Ren, Exploring properties in reduced Collatz dynamics, IEEE Dataport, 2018.  http://dx.doi.org/10.21227/ge9h-8a77 (2018).

Wei Ren, Verifying whether extremely large integer guarantees Collatz conjecture (can return to 1 finally), IEEE Dataport, http://dx.doi.org/10.21227/fs3z-vc10 (2018).

Wei Ren, Exploring the ratio between the count of x/2 and the count of (3*x+1)/2 in original dynamics for extremely large starting integers asymptotically, IEEE Dataport. http://dx.doi.org/10.21227/rxx6-8322 (2018).

Wei Ren, Exploring the inverse mapping from a dynamics to a residue class - inputting a reduced dynamics or partial dynamics and outputting a residue class , IEEE Dataport. http://dx.doi.org/10.21227/qmzw-gn71 (2018).

Wei Ren, Reduced Collatz Dynamics for Integers from 3 to 999999, IEEE Dataport. http://dx.doi.org/10.21227/hq8c-x340 (2018).

Wei Ren, Collatz Automata and Compute Residue Class from Reduced Dynamics by Formula, IEEE Dataport. http://dx.doi.org/10.21227/7z84-ms87 (2018).