# A New Approach on Proving Collatz Conjecture

Authors: Wei Ren
Journal: Journal of Mathematics
 (2019)

---

## Abstract

Collatz Conjecture (3x+1 problem) states any natural number x will return to 1 after 3⁎x+1 computation (when x is odd) and x/2 computation (when x is even). In this paper, we propose a new approach for possibly proving Collatz Conjecture (CC). We propose Reduced Collatz Conjecture (RCC)—any natural number x will return to an integer that is less than x. We prove that RCC is equivalent to CC. For proving RCC, we propose exploring laws of Reduced Collatz Dynamics (RCD), i.e., from a starting integer to the first integer less than the starting integer. RCC can also be stated as follows: RCD of any natural number exists. We prove that RCD is the components of original Collatz dynamics (from a starting integer to 1); i.e., RCD is more primitive and presents better properties. We prove that RCD presents unified structure in terms of (3⁎x+1)/2 and x/2, because 3⁎x+1 is always followed by x/2. The number of forthcoming (3⁎x+1)/2 computations can be determined directly by inputting x. We propose an induction method for proving RCC. We also discover that some starting integers present RCD with short lengths no more than 7. Hence, partial natural numbers are proved to guarantee RCC in this paper, e.g., 0 module 2; 1 module 4; 3 module 16; 11 or 23 module 32; 7, 15, or 59 module 128. The future work for proving CC can follow this direction, to prove that RCD of left portion of natural numbers exists.


---

## Body

## 1. Introduction

The Collatz Conjecture is a mathematical conjecture that is first proposed by Lothar Collatz in 1937. It is also known as the3x+1 conjecture, the Ulam conjecture, the Kakutani’s problem, the Thwaites conjecture, or the Syracuse problem [1–3]. “Mathematics may not be ready for such problems”, Paul Erdos once speculated about the Collatz Conjecture [4].The conjecture can be stated simply as follows: take any positive integer numberx. 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 number (i.e., x) is taken, the process will always eventually reach 1. The longest progressions for initial starting numbers of less than 10 billion and 100 quadrillion are calculated by Gary T. Leavens [5] and R. E. Crandall [6], respectively. Wei Ren et al. verified 2100000-1 can return to 1 after 481603 times of 3∗x+1 computation, and 863323 times of x/2 computation, which is the largest integer being verified in the world [7]. So far no one has tried to figure out whether all of the positive numbers eventually reach one, but we know that most of them do so. In particular, Krasikov and Lagarias proved that the number of integers finally reaching one in the interval [1,x] is at least proportional to x 0.84 [8].The paper is organized as follows: Section2 presents our Reduced Collatz Conjecture. A mathematical induction for proving Collatz Conjecture is proposed in Section 3. Section 4 introduces CODE(x) for representing reduced dynamics of x and explores its properties. Section 5 studies all starting numbers whose lengths of reduced dynamics are no more than 7. Finally, Section 6 concludes the paper.Notations(1)
Z: the set of integers. (2)
N = { a ∣ a ∈ Z , a ≥ 0 }. (3)
N ∗ = N ∖ { 0 } = { a ∣ a ∈ Z , a ≥ 1 } . (4)
[ 1 ] 2 = { x ∣ x ≡ 1   m o d   2 , x ∈ N ∗ } . (5)
[ 0 ] 2 = { x ∣ x ≡ 0   m o d   2 , x ∈ N ∗ } . (6)
[ i ] m = { x ∣ x ≡ i   m o d   m ,  x ∈ N ∗ ,  m ≥ 2,  m∈N∗,0≤i≤m-1,i∈N}. (7)
C T , C T ( · ): Collatz transformation. CT(x)=TPO(x) or H(x) according to the parity of current inputting x; CT(x)=I(x) or O(x) according to the parity of current inputting x. (8)
T P O , T P O ( · ): TPO(x)=3∗x+1 when x∈[1]2. (9)
H , H ( · ): H(x)=x/2 when x∈[0]2. (10)
C C: Collatz Conjecture. (11)
R C C: Reduced Collatz Conjecture. (12)
x ∈ R T N: x∈N∗ is Returnable. (13)
I , O , I ( · ) , O ( · ): I(x)=H(TPO(x))=(3∗x+1)/2, O(x)=H(x)=x/2, I0(x)=x,In(x)=In-1(I(x)), O0(x)=x,On(x)=On-1(O(x)),n∈N∗. (14)
C O D E ( x ): reduced dynamics or code for x. (15)
C O D E = { c ∣ c = C O D E ( x ) ,  x ∈ N ∗ } . (16)
c o d e: the length of code; e.g., if a code consists of I or O, it will be the number of I,O in the ordered sequence {I,O}≥1. (17)
A ∥ B: concatenation of A∈{I,O}≥a and B∈{I,O}≥b. a∈N∗,b∈N, or a∈N,b∈N∗, A∥{I,O}0=A, {I,O}0∥B=B. (18)
S = { ⋯ } returns the number of elements in a set S. (19)
m a x ( S = { } ), max(a,b) returns the maximal value in a set S, and the larger one in a,b, respectively. (20)
[ i 1 , i 2 , … , i n ] m = ⋃ j = 1 n ‍ [ i j ] m . (21)
X c: current transformed number.


## 2. Reduced Collatz Conjecture

Definition 1 (Collatz transformation).
(1) C T x = T P O x = 3 ∗ x + 1 x ∈ 1 2 H x = x 2 x ∈ 0 2T P O ( x ) can be simply denoted as TPO, and H(x) can be simply denoted as H.We assumeCT0(x)=x. Let CTn(x)=CT(CTn-1(x)),n∈N∗.Definition 2 (Collatz Conjecture (CC)).
∀ x ∈ N ∗, ∃L∈N∗, such that CTL(x)=1.Whenx=1, CC is held (i.e., 1→4→2→1). Thus, ∃L=3, CT3(1)=H(H(TPO(1)))=H(H(4))=H(2)=1. CT3∈{TPO,H}3. More specifically, here corresponding CT3 for x=1 is anordered sequenceTPO,H,H. Here “ordered sequence” implies that the parity of CTn-1(x) determines whether the intermediately forthcoming CT is TPO or H.In the following, we mainly are concerned withx≥2,x∈N∗.We give the Reduced Collatz Conjecture as follows.Definition 3 (Reduced Collatz Conjecture (RCC)).
∀ x ∈ N ∗ , x ≥ 2, ∃L∈N∗, such that CTL(x)<x and CTi(x)≮x,i=0,1,…,L-1.That is, the minimalL such that CTL(x)<x is of interest, since CTi(x)≮x,i=0,1,…,L-1.Proposition 4.
C C ⇔ R C C.Proof.
∀ x , L ∈ N ∗ ,  x ≥ 2, and it is obvious that CTL(x)∈N∗, i.e., CTL(x)≥1.
(1) SupposeCC is true. That is, ∀x∈N∗,x≥2, ∃L∈N∗, CTL(x)=1<x. Thus, RCC is true.
(2) Inversely, supposeRCC is true. That is, ∀x∈N∗,x≥2, ∃q0∈N∗, CTq0(x)<x.
IfCTq0(x)=1, then CC is true.
IfCTq0(x)>1, then let y1=CTq0(x). As RCC is true, ∃q1∈N∗, CTq1(y1)<y1.
Lety0=x. Iteratively, if yi=CTqi-1(yi-1)=1,i∈N∗, then CC is true. If yi=CTqi-1(yi-1)>1, then ∃qi∈N∗, yi+1=CTqi(yi)<yi.
Thus,yi+1<yi<…<y1<y0=x. yi,i∈N∗ is astrictly decreasing serial.
Besides,yi+1=CTq0+q1+q2+⋯+qi(x)≥1.
Therefore, after finite times of iterations,∃n∈N∗, yn=1.
That is,∃q=q0+q1+⋯+qn-1=∑i=0n-1qi∈N∗, CTq(x)=1.
Thus,CC is true.Remark 5.
(1)
x is called starting number, and x after transformation (e.g., CTi(x),i=1,2,…,q) is called transformed number. (2)
We call an ordered sequenceCTq∈{TPO,H}q in above proof asoriginal dynamics (as CTq(x)=1). Simply speaking, original dynamics of a starting number x is represented by (or composed of) a serial of occurred Collatz transformations during the procedure from the starting number (i.e., x) to 1. For example, the dynamics of5 (i.e., occurred transformations during the procedure from 5 to 1) is 5→16→8→4→2→1. That is, original dynamics of 5 is TPO,H,H,H,H. (3)
In contrast, we callCTq0∈{TPO,H}q0 in the above proof asreduced dynamics (as CTq0(x)<x). Simply speaking, reduced dynamics of a starting number x is represented by (or composed of) a serial of occurred Collatz transformations during the procedure from the starting number (i.e., x) to thefirst transformed number that is less than the starting number (i.e., x). For example, the reduced dynamics of 5 (i.e., occurred transformations during the procedure from 5 to the first transformed number less than the starting number, namely, 4) is5→16→8→4, in other words, TPO,H,H.Note that reduced dynamics is more primitive than original dynamics, because original dynamics consists of reduced dynamics. It can be easily observed from the proof of Proposition4. Nonetheless, we formally prove it in Proposition 6 as follows.Proposition 6.
∀ x 1 ∈ N ∗ , x 1 ≥ 2, if ∃L∈N∗ such that CTL(x1)=1; then, ∃li∈N∗,i=1,2,…,n, such that CT(∑i=1nli)=L(x1)=1 and xi+1=CTli(xi)<xi,xi∈N∗.Proof.
(1)CTL(x1)=1 and x1≥2; thus, ∃l1∈N∗,l1≤L such that CTl1(x1)<x1.
(2) Letx2=CTl1(x1). If x2>1, then ∃L′=L-l1∈N∗ such that CTL′(x2)=1. Thus, similarly to (1), ∃l2∈N∗,l2≤L′ such that CTl2(x2)<x2.
(3) Iteratively, computeli in the above way. Thus, x1, x2=CTl1(x1), x3=CTl1+l2(x1),..., CTl1+l2+…(x1) is a strictly decreasing serial. Besides, CT≥1(x)≥1, thus ∃n∈N∗, CTl1+l2+…+ln(x1)=1. Therefore, CT(∑i=1nli)=L(x1)=1 and xi+1=CTli(xi)<xi,xi∈N∗, i=1,2,…,n.Due to above proposition, we concentrate on reduced dynamics, which is a component of original dynamics.


## 3. Induction

This section is not preliminary for the rest of the paper, but it presents a formal mathematical induction related to Reduced Collatz Conjecture.To simplify the statement for conjecture, we define “Returnable” as follows.Definition 7 (Returnable).
x ∈ N ∗ is Returnable (denoted as x∈RTN), if and only if ∃L∈N∗ such that CTL(x)=1.The Collatz Conjecture will be true, if the following mathematical induction can be proved.Induction (for Collatz Conjecture)(1)
x = 1 ∈ R T N (recall that 1→4→2→1). (2)
If∀x≤k (where x,k∈N∗) is Returnable, then x=k+1 will be Returnable. That is, if x∈RTN (where x≤k,x,k∈N∗), then x=k+1∈RTN can be proved.In shorthand, the induction is as follows.(2)x∈RTN⇒x=k+1∈RTN,∀x≤k, where x,k∈N∗.Therefore, weonly need to check whether current transformed number is less than designated starting number. Once current transformed number is less than the starting number, the starting number will be Returnable (i.e., x=k+1∈RTN) due to the induction assumption (∀x≤k,x∈RTN).Figure1 illustrates the rationale in our induction.Figure 1
Induction rationale. Once current transformed number is less than the starting number, the starting number will be called “Returnable”. That is, onceCTCT…CTx<x, then x∈RTN.Proposition 8.
If the induction (especially, Step 2) can be proved, Collatz Conjecture is True.Proof.
Straightforward.Besides, it is trivial to check thatk=1,x=k=1∈RTN,x=k+1=2∈RTN.Ifk is odd in the induction, the induction is trivial to be proved. We state it as a proposition as follows.Proposition 9.
(3) x ∈ R T N ⇒ x = k + 1 ∈ R T N ,  ∀ x ≤ k ,where x∈N∗,k∈[1]2.Proof.
k ∈ [ 1 ] 2, thus k+1 is even. That is, when x=k+1, CT(x)=(k+1)/2≤k. ∀x≤k,x∈RTN, so CT(x)∈RTN. Thus, x=k+1∈RTN.Therefore, for the proof of induction we only need to prove the case thatk is even.If in the inductionk is even with k=4t,t∈N∗, the induction is straightforward to be proved. We state it as a proposition as follows.Proposition 10.
(4) x ∈ R T N ⇒ x = k + 1 ∈ R T N ,  ∀ x ≤ k ,where x∈N∗,k=4t,t∈N∗.Proof.
k = 4 t ,  t ∈ N ∗ . Thus, k+1=4t+1∈[1]2. Next, let us check whether x=k+1∈RTN. CT(k+1)=(3(4t+1)+1)=12t+4∈[0]2, CT(CT(x))=(12t+4)/2=6t+2∈[0]2, CT(CT(CT(x)))=(6t+2)/2=3t+1≤4t. As ∀x≤k=4t is Returnable, CT(CT(CT(x)))∈RTN. Thus, x=k+1∈RTN.Therefore, we only need to prove the case thatk is even with k=4t+2,t∈N in the induction due to the above Propositions 9 and 10. We give reduced version of induction as follows.Induction (Reduced Version of Induction for Collatz Conjecture)(1)
x = 1,2 , 3,4 , 5,6 ∈ R T N (Straightforward). (2)
If∀x≤k=2t+1 (x,k,t∈N∗) is Returnable, then x=k+1 will be Returnable. That is, if x∈RTN (x≤k=2t+1,x,k,t∈N∗), then x=k+1∈RTN can be proved. (3)
If∀x≤k=4t (x,k,t∈N∗) is Returnable, then x=k+1 will be Returnable. That is, if x∈RTN (x≤k=4t,x,k,t∈N∗), then x=k+1∈RTN can be proved. (4)
If∀x≤k=4t+2 (x,k,t∈N∗) is Returnable, then x=k+1 will be Returnable. That is, if x∈RTN (x≤k=4t+2,x,k,t∈N∗), then x=k+1∈RTN can be proved.As Steps (2) and (3) can be proved by Propositions9 and 10, respectively. In shorthand, the reduced version of induction for Collatz Conjecture that needs to be proved is only Step (4) as follows:(5)x∈RTN⇒x=k+1∈RTN,∀x≤k=4t+2,where x,k,t∈N∗.


## 4. CODE(x) and Its Properties

Theorem 11.
H always follows after TPO in CT≥1(x∈N∗).Proof.
In the definition ofCT(·), when x∈[1]2, CT(x)=TPO(x)=3∗x+1, which is even obviously. Thus, next CT(·) must be H(·) consequently. Therefore, H always follows after TPO.Therefore, we introduce new notations (i.e.,I and O) for simplicity.(1)
H always occurs after TPO; thus, H(TPO(x)) can be written together and denoted as I(x). That is, I(x)=H(TPO(x))=(3∗x+1)/2.(2)
O(·) is used to denote H(·) (for better vision contrastively).(3)
I and O may also be called Collatz transformations.For example, reduced dynamics ofx=5 are TPO,H,H. The transformation procedures are TPO(x), H(TPO(x)), and H(H(TPO(x))). It can also be simplified as I(x) and O(I(x)). Thus, reduced dynamics of x=5 can be written as I,O or “IO” in short.Besides,O(I(x)) can be simply written as IO(x). That is, IO(x)=O(I(x)), where IO(·) is a composite function, e.g., IO(5)=O(I(5))=O((3∗5+1)/2)=O(8)=8/2=4<5. Formally, CT1∥CT2∥⋯∥CTn(x)=CTn(CTn-1(…CT2(CT1(x)))), where CTi∈{I(·),O(·)},i=1,2,…,n.Definition 12.
∀ x ∈ N ∗, x≥2, if ∃L∈N∗ such that CTL(x)<x and CTi(x)≮x,i=0,1,…,L-1, where CT(·)∈{I(·),O(·)}, then let c=CTL∈{I,O}L and c is called
code (or reduced dynamics) forx, denoted as CODE(x)=CTL=c.Note thatCTL∈I,OL is an ordered sequence consisting of I and O. Besides, CTL=CTL-1∥CT,L≥2,CTL(x)=CT(CTL-1(x)). Recall that CT0(x)=x. Furthermore, this sequence implicitly matches theparity of all intermediate transformed numbers that are taken as input of CT(·).For example,CODE(x=5)=IO implies the following results:(1)
IO(5)=(3∗5+1)/2/2=4<5;(2)
I(5)=(3∗5+1)/2=8≮5;(3)
“I” is due to 5∈[1]2;(4)
“O” is due to I(5)=(3∗5+1)/2=8∈[0]2.Theorem 13.
∀ x ∈ N ∗, x≥2, if ∃L∈N∗, such that CTL(x)<x and CTi(x)≮x,i=0,1,…,L-1, where CT(·)∈{I(·),O(·)}, and letting c=CTL∈{I,O}L, then c is unique.
That is,(6)c∣x,L∈N∗,x≥2,CTLx<x,CTix≮x,i=0,1,…,L-1,CT·∈I·,O·,c=CTL=1.Proof (straightforward).
∀ x ∈ N ∗, ∃L∈N∗, such that CTL(x)<x, where CT∈{I,O}; let c=CTL∈{I,O}L. Given x, either I(x) or O(x) is deterministic and unique. Similarly, given x, CTi(x),i=1,2,…,L is deterministic and unique. (Recall that, the parity of CTi(x) determines the intermediately forthcoming transformation). Thus, c is unique for any given x.Remark 14.
(1)
We assumeCODE(x=1)=IO, although IO(1)=O((3∗1+1)/2)=O(2)=2/2=1≮x. In other words, the code for x=1 is IO. {c∣c=CODE(1)}={c∣c=IO}=1. In the following, we are always concerned with {x∣x≥2,x∈N∗}. (2)
IfL=c is finite for x (· returns the length of c, or the number of I and O in the ordered sequence c∈{I,O}≥1), then CODE(x) exists; if CODE(x) exists, then L is finite. (3)
IfRCC is true, then ∀x∈N∗, CODE(x) exists; if ∀x∈N∗, CODE(x) exists, then RCC is true. (4)
InCODE(x), x is called starting number. CTi(x),i=1,2,…,L,L=c are called transformed numbers. CTL(x) is the first transformed number that is less than the starting number x. That is, CTi(x)≮x,i=0,1,…,L-1, and CTL(x)<x. Besides, the parity of CTi(x) determines the selection of the intermediately next CT(·)∈{I(·),O(·)} after CTi. (5)
EachI(·) includes one TPO(·) computation since I(·)=H(TPO(·)). We denote the count of I(·) in CODE(x) as U. It equals the count of TPO or 3∗x+1 in the reduced dynamics of x. As TPO(x)=3∗x+1>x, roughly speaking, U indeed equals the times of “goingUp (becoming larger)” in the reduced dynamics of x. (6)
EachI(·) includes one H(·) computation, and O(·) itself is one H(·) computation. We denote the count of H(·) in CODE(x) as D. It equals the count of H or x/2 in the reduced dynamics of x. As H(x)=x/2<x, roughly speaking, D indeed equals the times of “goingDown (becoming smaller)” in the reduced dynamics of x. Note that the count of I(·) and O(·) in CODE(x) also equals D. In other words, D equals the length of CODE(x). That is, D=CODEx. (7)
We do not assume the existence ofCODE(x) for ∀x∈N∗, which is exactly what needs to be proved in Reduced Collatz Conjecture. We introduce notationCODE(x) for the following reasons:
(i)
The presentation will be more convenient. (ii)
C O D E ( x ∈ [ 3,99999999 ] ) are outputted by our computer program. We may discover some properties in them by observation, and they will be proved formally. (iii)
We can explore inner laws forCODE(x) without the detail of x (independent to x).The following propositions again confirm Propositions9 and 10.Proposition 15.
C O D E ( { x ∣ x ∈ [ 0 ] 2 } ) = O, CODE({x∣x∈[1]4})=IO.Proof.
(1)x∈[0]2, thus H occurs. x/2<x, thus CODE(x)=O.
(2) Ifx=1, CODE(1)=IO (by assumption).
Ifx≥2, x=4t+1∈[1]2, where t∈N∗. Thus, I occurs. I(x)=(3∗x+1)/2=(3∗(4t+1)+1)/2=(12t+4)/2=2∗(3t+1)∈[0]2. 2∗(3t+1)>x=4t+1, thus further transformation occurs. O(I(x))=2∗(3t+1)/2=3t+1<4t+1=x(∵t∈N∗), thus CODE(x)=IO.
In summary,(7)CODEx=Ox∈02,IOx∈14.(In the following,CODE({x∣x∈[i]m}) is shortened as (x∈[i]m), m≥2,m∈N∗,0≤i≤m-1,i∈N.)IfCODE(x∈N∗) exists, they can be looked as a whole - CODE={c∣c=CODE(x),x∈N∗}, and CODE presents certain properties.Proposition 16.
IfCODE(x∈[3]4) exists, then CODE(x)=IpO∥I,O≥1,p≥2.Proof.
Lettingx=4t+3, t∈N. Obviously, x∈[1]2.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2.
I 2 ( x ) = I ( I ( x ) ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8.
(1) Ift∈[0]2∪{0}, then 9t+8∈[0]2. Thus, the next transformation is “x/2”. Thus, the first five Collatz transformations are “IIO” (i.e., “TPO,H,TPO,H,H”). Besides, IIO(x)=(9t+8)/2=4.5t+4>4t+3=x. Further transformation thus occurs. Hence, if CODE(x) exists, then CODE(x)=I2O∥I,O≥1.
(2) Ift∈[1]2, then 9t+8∈[1]2. Thus, the first six Collatz transformations are “III” (i.e., “TPO,H,TPO,H,TPO,H”). Besides, III(x)=(3(9t+8)+1)/2=(27t+25)/2=13.5t+12.5>4t+3=x. Further transformation occurs. Hence, if CODE(x) exists, then CODE(x)=I3∥I,O≥1.
IfIII(x)∈[1]2, then more “I” occurs. Obviously, IIII(x)>x. Further transformation occurs. Hence, if CODE(x) exists, then CODE(x)=I4∥I,O≥1. If III(x)∈[0]2, then IIIO(x)=(13.5t+12.5)/2=6.75t+6.25>4t+3=x. Further transformation occurs consequently. Hence, if CODE(x) exists, then CODE(x)=I3OI,O≥1.
SupposeCODE(x)=CTL∈I,OL. There exists at least one “O” in L transformations; otherwise, CTL(x)=IL(x)>IL-1(x)>…>I(x)>x, which contradicts with CTL(x)<x. Besides, IpO(x)=Ip(x)/2>Ip-1(x)/2=Ip-1O(x)>…>IIO(x)>x, p≥3; thus, after IpO(p≥3) further transformation occurs.
In summary, ifCODE(x∈[3]4) exists, then CODE(x)=IpO∥I,O≥1,p≥2.Next corollary states thatCODE(x) (or CODE) presents unified format.Proposition 17.
C O D E ( x ) ∈ F O R M A T = I p O I , O q, where p,q∈N. More specifically,(8)p=0,q=0x∈02,p=1,q=0x∈14,p=2,q≥1x∈38,p≥3,q≥1x∈78.Proof.
We here assumeI0∥O=O and O∥{I,O}0=O. According to Propositions 15 and 16, we have(9)p=0,q=0x∈02,p=1,q=0x∈14,p=2,q≥1x=4t+3,t∈02∪0,p≥3,q≥1x=4t+3,t∈12.
It can be written as follows.
(1)p=0,q=0 as CODE(x∈[0]2)=O; p=1,q=0 as CODE(x∈[1]4)=IO.
(2)p=2,q≥1 when x∈[3]8 as {x∣x=4t+3,t∈[0]2∪{0}}={x∣x=4∗2k+3,k∈N}=[3]8.
(3)p≥3,q≥1 when x∈[7]8, as {x∣x=4t+3,t∈[1]2}={x∣x=4(2k+1)+3,k∈N}=[7]8.
Thus, (9) can be rewritten as (8).More specifically, we have the following theorem that give more details onp.Theorem 18 (format theorem).
C O D E ( x ) ∈ F O R M A T = I p O I , O q, where p,q∈N. Besides,(10)p=0x∈02,1x∈14,2x∈38x=4t+3,t∈02∪0,α+2t+1=2α∗A,A∈12,α∈N∗,x∈78x=4t+3,t∈12.
q = 0 when p=0,1; q≥1 when p≥2.Proof.
q is trivial due to Proposition 17, so we are mainly concerned with p.
By Proposition15 or (7), if x∈[0]2, then CODE(x)=O∈FORMAT and p=0. If x∈[1]4, then CODE(x)=IO∈FORMAT and p=1.
Next, we concentrate onx∈[3]4.
C O D E ( 3 ) = I I O O = I 2 O 2, which can be manually and easily verified.
Letx=4t+3,t∈N∗.
(  1) Case I: t ∈ [ 0 ] 2. As x=4t+3∈[1]2, I(·) is conducted consequently. As I(x)=(3x+1)/2=1.5x+1.5>x and II(x)>I(x)>x, the checking on whether current transformed number is less than starting number may be omitted in some straightforward cases.
I ( x ) = ( 3 x + 1 ) / 2 = ( 3 ( 4 t + 3 ) + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2; thus, transformation I(·) is conducted consequently.
I ( I ( x ) ) = I I ( x ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = ( 18 t + 16 ) / 2 = 9 t + 8 ∈ [ 0 ] 2 . Thus, O(·) is conducted consequently.
O ( I ( I ( x ) ) ) = I I O ( x ) = ( 9 t + 8 ) / 2 = 4.5 t + 4 > 4 t + 3 . Thus, further transformation is conducted consequently.
Therefore,CODE(x)=I2O∥I,O≥1∈FORMAT.
(  2) Case II: t ∈ [ 1 ] 2. As x=4t+3∈[1]2, I(·) is conducted consequently.
I ( x ) = ( 3 x + 1 ) / 2 = ( 3 ( 4 t + 3 ) + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2; thus, I(·) is conducted consequently.
I I ( x ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = ( 18 t + 16 ) / 2 = 9 t + 8 ∈ [ 1 ] 2 . Thus, I(·) is conducted consequently.
I I I ( x ) = ( 3 ( 9 t + 8 ) + 1 ) / 2 = ( 27 t + 25 ) / 2 . It depends on the partition of t (more specifically, t∈[1]4 or [3]4) whether (27t+25)/2 is even or odd.
(It comes from following observations:(27t+25)/2∈[0]2⇐(27t+25)/2=2k, k∈N∗⇐27t+25=4k⇐27t∈[3]4⇐3t∈[3]4⇐t∈[1]4.)
(2.1) Ift∈[1]4, III(x)=(27t+25)/2=(27∗(4∗k+1)+25)/2=(108k+52)/2=54k+26∈[0]2 (k∈N∗); thus, O(·) will occur consequently.
(2.2) If∈[3]4, III(x)=(27t+25)/2=(27∗(4∗k+3)+25)/2=(108k+106)/2=54k+53∈[1]2; thus, I(·) will occur consequently.
Besides, suppose current transformed number is denoted asXc.
X c = I I I O ( x ) = ( 27 t + 25 ) / 2 / 2 = ( 54 k + 26 ) / 2 = 27 k + 13, whose parity depends on the parity of k.
X c = I I I I ( x ) = ( 3 ( 27 t + 25 ) / 2 + 1 ) / 2 = ( 3 ( 54 k + 53 ) + 1 ) / 2 = ( 162 k + 160 ) / 2 = 81 k + 80, whose parity depends on the parity of k.
In other words, the judgement on the parity ofXc is undecidable, unless the domain (t∈[1]4 or t∈[3]4) ispartitioned further.
For exploring more general results, we put it in another way as follows.
Suppose there exist at mostp times of “I” at code head (i.e., IpO…) for x∈[3]4. Observing following equation for Xc=Ip(x) after consecutive p≥2 times of “I”:(11)Xc=Ipx=3…33x+1/2+1/2…+1)2=3232…3232x+12+12+⋯+12+12=32px+1232p-1+32p-2+⋯+1=32px+123/2p-13/2-1=32px+32p-1=32px+1-1∵x=4t+3,t∈N=32p4t+3+1-1=3p2p-2t+1-1∈N∗.
Note that above computation implicitly includes two requirements due top times of consecutive I(·) as follows.
(i) All intermediate transformed numbers during processes (i.e., computingp times of consecutive “I”) satisfy(12)Xc=3i2i-2t+1-1∈12,where 2≤i≤p-1,i∈N∗.
(ii) Besides,(13)Xc=3i2i-2t+1-1∈02,where i=p, as only (or at most) p consecutive I(·) occur.
In other words,p can also be looked as the minimal value to let current transformed number Xc be in [0]2. Thus, we need to explore the requirement on p for given t such that(14)3i2i-2t+1-1∈122≤i≤p-1,3i2i-2t+1-1∈02i=p.
We call this requirement (i.e., (14)) as REQ.
Representt+1 as 2α∗A,A∈[1]2,α∈N∗. That is, t+1=2α∗A. Obviously, this representation is unique. We thus need to prove that REQ is satisfied if and only if p=α+2. Note that we will see that here p is indeed determined by α.
For2≤i<p=α+2,i∈N∗, we have α+2-i>0.(15)Xc=3i2i-2t+1-1=3i2i-2∗2α∗A-1=3i∗2α-i+2∗A-1.
α + 2 - i > 0 ⇒ 2 α - i + 2 ∈ [ 0 ] 2 ⇒ 3 i ∗ 2 α - i + 2 ∗ A ∈ [ 0 ] 2 ⇒ 3 i ∗ 2 α - i + 2 ∗ A - 1 ∈ [ 1 ] 2 .
Wheni=p=α+2, we have exactly(16)Xc=3p2p-2t+1-1=3p2p-2∗2α∗A-1=3p∗2α-p+2∗A-1=3p∗A-1∈02.∵A,3p∈12
It is easy to see thatp=α+2 is the one and only one for REQ, as desired.Corollary 19 (t determine p corollary).
Given starting numberx∈[3]4 (i.e., x=4t+3,t∈N), the number of consecutive “I” (denoted as p) is determined by t according to (17) as follows:(17)p=2t∈02,α+2α=log2t+1A∈N∗,A=maxa∣a∈12,a∣t+1,t∈12.Corollary 20.
Given starting numberx∈[3]4,t=(x-3)/4∈N, the first p times of Collatz transformations must be “I” and p can be determined by t by (17), and the transformed number after Ip transformations is(18)Ipx=32px+1-1=3p2p-2t+1-1∈N∗,p≥2.Proof.
It is straightforward due to (11), Theorem 18, and Corollary 19.
Alternatively, only to compute the transformed numberIp(x), we can prove it by induction as follows.
(1)p=2.(19)Ipx=I2x=33x+1/2+12=3232x+12+12=322x+32∗12+12=322x+3232-1+12=322x+322-32+12=322x+1-1=32px+1-1.
(2) Supposep=i; we have Ii(x)=(3/2)i(x+1)-1.(20)Ii+1x=IIix=33/2ix+1-1+12=3232ix+1-1+12=32i+1x+1-32+12=32i+1x+1-1.Remark 21.
(1) Note that, due to Corollary19, p for Ip in CODE(x) can be computed by t=(x-3)/4 and log2t+1/A directly without conducting concrete Collatz transformations, which can accelerate the computation of dynamics.
(2) Besides, by (11) or Corollary 20, if t=0, we then have p=2, because Ip(x)=(3p/2p-2)(t+1)-1=(3p/2p-2)-1∈N∗, which matches with the result CODE(3)=IIOO by manually computing.
(3) Indeed, (11) can be extended to include all cases (i.e., for p=0,1). If p=0, by assuming I0(x)=x, I0(x)=x=(3/2)0(x+1)-1=(3/2)p(x+1)-1; if p=1, I1(x)=I(x)=(3∗x+1)/2=(3/2)1(x+1)-1=(3/2)p(x+1)-1. Therefore, Ip(x)=(3/2)p(x+1)-1 for p∈N∗.Corollary 22.
Given starting numberx∈[1]2, the first p times of Collatz transformations must be “I” and p can be determined by x, and the transformed number after Ip transformations is(21)Ipx=32px+1-1,p≥1.Proof.
It is straightforward due to (11), Theorem 18, and Corollaries 19 and 20.
Ifx∈[1]4, then p=1, Ip(x)=I(x)=(3x+1)/2=(3/2)1(x+1)-1=(3/2)p(x+1)-1.
Ifx∈[3]4, then p≥2, Ip(x)=(3/2)p(x+1)-1 due to Corollary 20.Next corollary states that the head of code forx=2n-1,n∈N∗ is InO.Corollary 23.
(22) C O D E x = 2 n - 1 ,  n ∈ N ∗ ∈ I n O I , O ≥ 0 .Proof.
SupposeCODE(x)∈IpOI,O≥0, due to Theorem 18.
(1)n=1, x=2-1=1∈[1]4; thus, p=1 due to Theorem 18. Thus, CODE(21-1)∈I1OI,O≥0.
Indeed,CODE(x=1)=IO can be manually computed (recall that 1→4→2→1.)
(2)n∈N∗,n≥2, x=2n-1∈[3]4.
(2.1)n=2, x=22-1=3∈[3]8, or (x-3)/4=0∈[0]2∪{0}, thus p=2 due to Theorem 18. Thus, CODE(22-1)∈I2O{I,O}≥1.
Indeed,CODE(x=3)=IIOO=I2OO can be manually computed (recall that 3→10→5→16→8→4→2<3.)
(2.2)n>2, t=(x-3)/4=(2n-1-3)/4=2n-2-1∈[1]2.  t+1=2n-2. Thus, A=1. α=log2(t+1)/A=log22n-2=n-2. Thus, p=α+2=n-2+2=n. Hence, CODE(x)∈InOI,O≥1 owing to Theorem 18.
Summarizing (1) and (2),CODE(x=2n-1,n∈N∗)∈InO{I,O}≥0.Example 24.
(1)x=7. 7→22→11→34→17→52→26→13→40→20→10→5. Thus, CODE(7)=IIIOIOO=I3OIOO.
(2)x=15. 15→46→23→70→35→106→53→160→80→40→20→10. Thus, CODE(15)=IIIIOOO=I4OOO.Proposition 25.
C O D E ∈ { I , O } ≥ 0 ∥ O. (That is, CODE must end with “O”, or the last transformation in CODE is “O”.)Proof (straightforward).
It can be easily understood intuitively. That is, reduced dynamics should be ended by “going Down”, not “going Up” (recall items(5) and (6) in Remark 14).
IfCODE ends by “I”, suppose ∃x∈N∗, x≥2, c(x)≮x, CODE(x)=c∥I.
{ c ∥ I } ( x ) = I ( c ( x ) ) = ( 3 ∗ c ( x ) + 1 ) / 2 = 1.5 c ( x ) + 0.5 = c ( x ) + 0.5 c ( x ) + 0.5 > c ( x ); thus, CODE(x)={c∥I}(x)≮x. Contradiction occurs.
Put it in another way, if{c∥I}(x)<x, then I(c(x))<x. Together with I(c(x))>c(x), we have c(x)<x. Thus, reduced dynamics of x ends after c and CODE(x)=c≠c∥I.Next corollary gives more details onCODE(x∈[3]4) that has a unified form as (23)Ip0≥2Oq0≥1Ip1≥1Oq1≥1…Ipn≥1Oqn≥1.That is, each code consists of one or more segments, and each segment has a unified form as IpOq,p≥1,q≥1.Corollary 26.
(24) C O D E x ∈ 3 4 ∈ I p 0 ≥ 2 O q 0 ∥ I p i O q i ≥ 0 ,where p0,q0,i,pi,qi∈N∗.Proof (straightforward).
x ∈ [ 1 ] 2, thus I occurs. After p times of I transformations, Ip(x)∈[0]2 and thus O follows. After q times of O transformations, IpOq(x)∈[1]2, thus I occurs. Indeed, q can be determined by Ip(x) by q=log2Ip(x)/B, B=max({b∣b∈[1]2,b∣Ip(x)}).
Iteratively, each segment has a unified formIpOq, where p,q∈N∗.
The first segment is listed solely, because the distinction between the first segment and the other segments is thatp0≥2 but pi≥1,i∈N∗. (In other words, when and only when an intermediate transformed number Xc∈[1]4 occurs, pi=1. Otherwise, pi≥2.)Put it in another way, if intermediate transformed numbers in[1]4 during reduced dynamics are tackled explicitly, we have the following corollary.Corollary 27.
(25) C O D E x ∈ 3 4 ∈ I p 0 ≥ 2 O q 0 ∥ I O q i , I p i ≥ 2 O q i ≥ 0 .where p0,q0,i,pi,qi∈N∗.


## 5. Short Codes -{(x,c)∣c=CODE(x),c≤7}

In this section, we explorex and their codes whose length is less than 7, called short codes. The exploration of this section helps build empirical understanding for Sections 3 and 4 (e.g., induction and CODE(x)). Before the exploration, a lemma is given as preliminaries as follows.Lemma 28.
m ∈ N ∗ ,  m ≥ 2 ,  0 ≤ i ≤ m - 1 , a , b , x ∈ N ∗.
(1)x∈[i]m⇒a∗x+b∈[(a∗i+b)modm]m;
(2)m,i∈[0]2,x∈[i]m⇒x/2∈[i/2]m/2;
(3)m,(a∗i+b)/2∈[0]2, x∈[i]m⇒(a∗x+b)/2∈[((a∗i+b)modm)/2]m/2.Proof.
(1)x∈[i]m⇒x=k∗m+i,k∈N
⇒ a ∗ x + b = a∗k∗m+i+b=a∗k∗m+a∗i+b
⇒ a ∗ x + b ≡ a∗i+bmodm∵a∗k∈N
⇒ a ∗ x + b ∈ [ ( a ∗ i + b )   m o d  m ] m.
(2)x∈[i]m⇒x=k∗m+i,k∈N
⇒ x / 2 = k ∗ m / 2 + i / 2   ∵ m, i∈[0]2
⇒ x / 2 ∈ [ i / 2 ] m / 2.
(Besides,0≤i≤m-1,m,i∈[0]2⇒0≤i≤m-2⇒0≤i/2≤(m-2)/2=m/2-1.)
(3) The proof is the combination of above (1) and (2).
Specifically,x∈[i]m⇒a∗x+b∈[(a∗i+b)modm]m
⇒ ( a ∗ x + b ) / 2 ∈ [ ( ( a ∗ i + b )   m o d  m ) / 2 ] m / 2
∵ m, (a∗i+b)/2∈[0]2⇒((a∗i+b)modm)∈[0]2.Proposition 29.
C O D E ( x ) = I I O O, if(26)x∈x∣x∈34,t=x-34∈0∪04=x∣x=4∗4k+3=16k+3,k∈N=316.Proof.
x = 4 t + 3 ∈ [ 1 ] 2.
I ( x ) = ( 3 x + 1 ) / 2 = ( 3 ( 4 t + 3 ) + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2, and I(x)=6t+5>4t+3=x. Thus, “I” occurs consequently.
I I ( x ) = I ( 6 t + 5 ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ ( 9 ∗ 0 + 8 )   m o d  4 ] 4 = [ 0 ] 4. Thus, “OO” occurs consequently.
AsIIOO(x)=OO(9t+8)=(9t+8)/2/2=2.25t+2<3t+2<4t+3=x, the codeends hereby with “IIOO”. That is, CODE(x∈[3]16)=IIOO.Example 30.
115 → 346 → 173 → 520 → 260 → 130 → 65 < 115 . Thus, CODE(115)=IIOO. It can be verified that x=115∈[3]16,t=(115-3)/4=28∈[0]4.Proposition 31.
C O D E ( x ) = I I O I O, if(27)x∈x∣x∈34,t=x-34∈28=x∣x=48k+2+3=32k+11,k∈N=1132.Proof.
x = 4 t + 3 ∈ [ 1 ] 2.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2.
I I ( x ) = I ( 6 t + 5 ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ ( 2 ∗ 9 + 8 )   m o d  8 ] 8 = [ 2 ] 8 ⊂ [ 0 ] 2 due to Lemma 28 (1). “O” occurs consequently.
I I O ( x ) = ( 9 t + 8 ) / 2 ∈ [ 2 / 2 ] 8 / 2 = [ 1 ] 4 ⊂ [ 1 ] 2 . Thus, next transformation is “I”. Besides, (9t+8)/2=4.5t+4>4t+3=x.
I I O I ( x ) = ( 3 ∗ 9 t + 8 / 2 + 1 ) / 2.  3∗9t+8/2+1∈[(3∗1+1)mod4]4=[0]4.  (3∗9t+8/2+1)/2∈[0]2. Thus, “O” occurs consequently.
I I O I O ( x ) = ( 3 ∗ 9 t + 8 / 2 + 1 ) / 2 / 2 = ( 13.5 t + 13 ) / 2 / 2 = (6.75t+6.5)/2 = 3.375t+3.25 = 4t+3+(0.25-0.625t) <4t+3=x; the code ends with “IIOIO”. That is, CODE(x∈[11]32)=IIOIO.Example 32.
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 < 11; CODE(11)=IIOIO, x=11∈[11]32,(11-3)/4=2∈[2]8.Proposition 33.
C O D E ( x ) = I I I O O, if(28)x∈x∣x∈34,t=x-34∈58=x∣x=48k+5+3=32k+23,k∈N=2332.Proof.
x = 4 t + 3 ∈ [ 1 ] 2, t∈[5]8.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2, thus next transformation is “I”.
I I ( x ) = I ( 6 t + 5 ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ ( 9 ∗ 5 + 8 )   m o d  8 ] 8 = [ 5 ] 8 ⊂ [ 1 ] 2, thus next transformation is “I”.
I I I ( x ) = I ( 9 t + 8 ) = ( 3 ( 9 t + 8 ) + 1 ) / 2. 3(9t+8)+1∈([(3∗5+1)mod8]8=[0]8. (3(9t+8)+1)/2∈[0]4, thus next transformations are double “O”.
Check whether current transformed number is less than the starting number as follows:
I I I O ( x ) = 27 t + 25 / 2 / 2 = ( 13.5 t + 12.5 ) / 2 = 6.75 t + 6.25 t > 4 t + 3 = x.
I I I O O ( x ) = ( 6.75 t + 6.25 ) / 2 = 3.375 t + 3.125 = 4 t + 3 + ( 0.125 - 0.625 t ) < 4 t + 3, as t≥1.Example 34.
55 → 166 → 83 → 250 → 125 → 376 → 188 → 94 → 47 < 55; CODE(55)=IIIOO, x=55∈[23]32,(55-3)/4=13∈[5]8.Proposition 35.
C O D E ( x ) = I I I O I O O, if
x ∈ { x ∣ x ∈ [ 3 ] 4 , t = ( x - 3 ) / 4 ∈ [ 1 ] 32 } = { x ∣ x = 4 ( 32 k + 1 ) + 3 = 128 k + 7 , k ∈ N } = [ 7 ] 128.Proof.
x = 4 t + 3 ∈ [ 1 ] 2 ,  t ∈ [ 1 ] 32.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2.
I I ( x ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ 9 ∗ 1 + 8 ] 32 = [ 17 ] 32 ⊂ [ 1 ] 2.
I I I ( x ) = ( 3 ( 9 t + 8 ) + 1 ) / 2 ∈ ( [ ( ( 3 ∗ 17 + 1 )   m o d  32 ) / 2 ] 32 / 2 = [ 10 ] 16 ⊂ [ 0 ] 2.
I I I O ( x ) ∈ [ 10 / 2 ] 16 / 2 = [ 5 ] 8 ⊂ [ 1 ] 2.
I I I O I ( x ) = I ( I I I O ( x ) ) ∈ [ ( ( 3 ∗ 5 + 1 )   m o d  8 ) / 2 ] 8 / 2 = [ 0 ] 4 . Thus, double “O” follow immediately. In summary, above occurred dynamics to current transformed number is thus IIIOIOO.
Next, we check whether it is the final code (or reduced dynamics is terminated at this transformed number) by checking whether current transformed number is less than the staring number (i.e.,x).
I I I ( x ) = ( 3 ( 9 t + 8 ) + 1 ) / 2 = ( 27 t + 25 ) / 2 = 13.5 t + 12.5 .
I I I O ( x ) = O ( I 3 ( x ) ) = ( 13.5 t + 12.5 ) / 2 = 6.75 t + 6.25 > 4 t + 3 = x .
I I I O I ( x ) = I ( I I I O ( x ) ) = ( 3 ( 6.75 t + 6.25 ) + 1 ) / 2 = ( 20.25 t + 18.75 + 1 ) / 2 = ( 20.25 t + 19.75 ) / 2 = 10.125 t + 9.875 .
I I I O I O ( x ) = O ( I I I O I ( x ) ) = ( 10.125 t + 9.875 ) / 2 = 5.0625 t + 4.9375 > 4 t + 3 = x .
I I I O I O O ( x ) = O ( I I I O I O ( x ) ) ) ) = ( 5.0625 t + 4.9375 ) / 2 = 2.53125 t + 2.46875 < 3 t + 3 < 4 t + 3 = x .
Therefore,CODE(x∈[7]128)=IIIOIOO, which can be also written as I3OIO2.Remark 36.
Indeed, (11) can be used for computing current transformed number (denoted as Xc) after I3(x) to simplify above process in the proof. After I3(x),
X c ⇐ ( 3 / 2 ) 3 ( x + 1 ) - 1 = 1 . 5 3 x + 1 . 5 3 - 1 = 3.375 x + 2.375,
X c ⇐ O ( X c ) = 0.5 ( 3.375 x + 2.375 ) = 1.6875 x + 1.1875,
X c ⇐ I ( X c ) = 1.5 ( 1.6875 x + 1.1875 ) + 0.5 = 2.53125 x + 2.28125,
X c ⇐ O ( X c ) = 0.5 ( 2.53125 x + 2.28125 ) = 1.265625 x + 1.140625,
X c ⇐ O ( X c ) = 0.5 ( 1.265625 x + 1.140625 ) = 0.6328125 x + 0.5703125 = x + ( 0.5703125 - 0.3671875 x ) < x, as x≥2 due to x∈[3]4.Example 37.
135 → 406 → 203 → 610 → 305 → 916 → 458 → 229 → 688 → 344 → 172 → 86 < 135; CODE(135)=IIIOIOO, x=135∈[7]128,(x-3)/4=(135-3)/4=33∈[1]32.The following two propositions originally stem from our observations on codes outputted by our computer programs.Proposition 38.
C O D E ( x ) = I I O I I O O, if(29)x∈x∣x∈34,t=x-34∈1432=x∣x=432k+14+3=128k+59,k∈N=59128.Proof.
x = 4 t + 3 ∈ [ 1 ] 2 , t ∈ [ 14 ] 32.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2, thus “I” will follow consequently.
I 2 ( x ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ ( 9 ∗ 14 + 8 )   m o d  32 ] 32 = [ 6 ] 32 ⊂ [ 0 ] 2, thus “O” will follow.
O ( I 2 ( x ) ) ∈ [ 6 / 2 ] 32 / 2 = [ 3 ] 16 ⊂ [ 1 ] 2, thus “I” will follow.
I ( O ( I 2 ( x ) ) ) ∈ ( [ ( 3 ∗ 3 + 1 ) / 2 ] 16 / 2 = [ 5 ] 8 ⊂ [ 1 ] 2, thus “I” will follow.
I 2 ( O ( I 2 ( x ) ) ) ∈ [ ( ( 3 ∗ 5 + 1 )   m o d  8 ) / 2 ] 8 / 2 = [ 0 ] 4, thus double “O” will follow.
Next, current transformed number will be compared with starting numberx.
I 2 x = 9 t + 8.
O ( I 2 ( x ) ) = ( 9 t + 8 ) / 2 = 4.5 t + 4 > 4 t + 3 = x.
I ( O ( I 2 ( x ) ) ) = ( 3 ( 4.5 t + 4 ) + 1 ) / 2 = ( 13.5 t + 13 ) / 2 = 6.75 t + 6.5.
I 2 ( O ( I 2 ( x ) ) ) = ( 3 ( 6.75 t + 6.5 ) + 1 ) / 2 = ( 20.25 t + 20.5 ) / 2 = 10.125 t + 10.25.
O ( I 2 ( O ( I 2 ( x ) ) ) ) = ( 10.125 t + 10.25 ) / 2 = 5.0625 t + 5.125 > 4 t + 3 = x.
O 2 ( I 2 ( O ( I 2 ( x ) ) ) ) = ( 5.0625 t + 5.125 ) / 2 = 2.53125 t + 2.5625 < 3 t + 3 < 4 t + 3 = x.
Therefore, the reduced dynamics ends with “IIOIIOO”. That is, CODE(x∈[59]128)=IIOIIOO=I2OI2O2.Proposition 39.
C O D E ( x ) = I I I I O O O, if(30)x∈x∣x∈34,t=x-34∈332=x∣x=432k+3+3=128k+15,k∈N=15128Proof.
x = 4 t + 3 ∈ [ 1 ] 2 ,  t ∈ [ 3 ] 32.
I ( x ) = ( 3 x + 1 ) / 2 = ( 12 t + 10 ) / 2 = 6 t + 5 ∈ [ 1 ] 2.
I 2 ( x ) = ( 3 ( 6 t + 5 ) + 1 ) / 2 = 9 t + 8 ∈ [ ( 9 ∗ 3 + 8 )   m o d  32 ] 32 = [ 3 ] 32 ⊂ [ 1 ] 2.
I 3 ( x ) ∈ [ ( 3 ∗ 3 + 1 ) / 2 ] 32 / 2 = [ 5 ] 16 ⊂ [ 1 ] 2.
I 4 ( x ) ∈ [ ( ( 3 ∗ 5 + 1 )   m o d  16 ) / 2 ] 16 / 2 = [ 0 ] 8, thus triple “O” will follow.
I 2 ( x ) = 9 t + 8.
I 3 ( x ) = ( 3 ( 9 t + 8 ) + 1 ) / 2 = ( 27 t + 25 ) / 2 = 13.5 t + 12.5.
I 4 ( x ) = ( 3 ( 13.5 t + 12.5 ) + 1 ) / 2 = ( 40.5 t + 38.5 ) / 2 = 20.25 t + 19.25.
O ( I 4 ( x ) ) ) = ( 20.25 t + 19.25 ) / 2 = 10.125 t + 9.625.
O 2 ( I 4 ( x ) ) ) = ( 10.125 t + 9.625 ) / 2 = 5.0625 t + 4.8125 > 4 t + 3 = x.
O 3 ( I 4 ( x ) ) ) = 2.53125 t + 2.40625 < 3 t + 3 < 4 t + 3 = x.
Therefore,CODE(x∈[15]128)=IIIIOOO=I4O3.In summary, aforementioned codes that have short lengths are listed in (31) as follows:(31)CODEx=IIOOx∈316,x-34=t∈04∪0,IIOIOx∈1132,x-34=t∈28,IIIOOx∈2332,x-34=t∈58,IIIOIOOx∈7128,x-34=t∈132,IIIIOOOx∈15128,x-34=t∈332,IIOIIOOx∈59128,x-34=t∈1432.Note that here short length meansCODEx is short, where · is the length of CODE(x) measured by the count of “I” and “O” in CODE(x). For example, CODE(x∈[3]16)=IIOO=4, CODE(x∈[11]32)=IIOIO=5.In summary, (7) and (31) are presented together in (32) (L=CODEx). It justifies that CODE is unique (recall Theorem 13), as all intersection sets for x in (32) are empty. The Format Theorem (Theorem 18) is confirmed as well.(32)CODEx=OL=1,x∈02,IOL=2,x∈14,IIOOL=4,x∈316,IIOIOL=5,x∈1132,IIIOOL=5,x∈2332,IIIOIOOL=7,x∈7128,IIIIOOL=7,x∈15128,IIOIIOOL=7,x∈59128.We discover that (32) enumerates all possible codes for {x∣L=CODEx≤7}.Proposition 40.
{ x ∣ L = C O D E x ≤ 7 } = { x ∣ x ∈ [ 0 ] 2 ∪ [ 1 ] 4 ∪ [ 3 ] 16 ∪ [11]32∪[23]32∪[7]128∪[15]128∪[59]128}.Proof.
IfCODEx=3, then CODE(x)=IIO because Format Theorem (Theorem 18) and CODE end by “O” (Proposition 25). However, IIO(x)=(3(3x+1)/2+1)/2/2=(3(1.5x+1.5)+1)/4=4.5/4x+5.5/4=1.125x+1.375>x. Thus, CODEx≠3.
IfCODEx=4, then CODE(x)=II{I,O}O because Format Theorem and CODE end by “O” (Proposition 25). Thus, CODE(x)=IIIO or CODE(x)=IIOO. As IIIO(x)=6.75t+6.25>4t+3=x (recall Proposition 35), CODE(x)=IIIO is impossible. Hence, there exists only one type of code for CODEx=4 (i.e., CODE(x)=IIOO).
Similarly, we can prove that there exists exactly two types of codes forCODEx=5, since CODE(x)=III,O2O. {I,O}2={IO,II,OO,OI}, but ∀x∈[3]4,IIIIO(x)>x and IIOO(x)<x. Thus, only “OI” and “IO” are possible. Similarly, we can prove that there exists three types of codes for CODEx=7.
Besides,CODEx=6 is impossible, as ∀x∈[3]4,IIIOIO(x)>x, IIIIOO(x)>x, IIOIIO(x)>x, IIOIO(x)<x, and IIIOO(x)<x (and by Format Theorem and Proposition 25).In the following, we use[i1,i2,…,in]m to denote ⋃j=1n[ij]m.Corollary 41.
LetS¯=[1]2∪[0]4∪[2]16∪[10,22]32∪[6,14,58]128. ∀x≤k,k∈S¯,x∈RTN⇒x=k+1∈RTN.Proof.
LetS=[0]2∪[1]4∪[3]16∪[11,23]32∪[7,15,59]128.
k ∈ S ¯ ⇒ k + 1 ∈ S ⇒ x ∈ S ∵ x = k + 1
⇒ ∃ C O D E x ⇒ ∃ L ∈ N ∗ , C T L x < x ∵ C O D E x = C T L
⇒ C T L x < k + 1 ∵ x = k + 1
⇒ C T L x ≤ k
⇒ C T L x ∈ R T N ∵ ∀ x ≤ k ,  x ∈ R T N
⇒ ∃ L ′ ∈ N ∗ , C T L ′ C T L x = 1
⇒ ∃ L ′ ′ = L ′ + L ∈ N ∗ , C T L ′ ′ x = 1
⇒ x ∈ R T N.Indeed,k∈[1]2∪[0]4 have already been discussed in Propositions 9 and 10. Recall that k∈[2]4 is the major concern in reduced version of induction for Collatz Conjecture; that is, ∀x≤k=4t+2,x∈RTN⇒x=k+1∈RTN, where x,k,t∈N∗. We can prove that portion of k=4t+2 in induction is Returnable as follows.Corollary 42.
LetS¯=[2]16∪[10,22]32∪[6,14,58]128.
∀ x ≤ k ,  k ∈ S ¯ ⊂ [ 2 ] 4 ,  x ∈ R T N ⇒ x = k + 1 ∈ R T N.In other words, we can prove that portion oft is Returnable as follows:Corollary 43.
LetT=[2,5]8∪[1,3,14]32.
∀ x ≤ k ,  k = 4 t + 2 ,  t ∈ T ,  x ∈ R T N ⇒ x = k + 1 ∈ R T N.Thus, we have already proved that portion of induction cases is Returnable. For the proof of Collatz Conjecture, we need to prove that all cases are Returnable. That is, all cases fork=4t+2 are Returnable to make S¯=[2]4, or all cases for t are Returnable to make T=N∗.Note that, indeed, without relying on the induction in Section3, we only need to prove ∀x∈N∗,x∈RTN. As CC is equivalent to RCC (recall Proposition 4), we thus solely need to prove RCC is true. In other words, ∀x∈N∗,∃CODE(x) (recall Remark 14 (3)).


## 6. Conclusion

In this paper, we propose a new direction for proving Collatz Conjecture, by proving Reduced Collatz Conjecture. Reduced Collatz Conjecture is equivalent to Collatz Conjecture but easier to explore for inherent properties. It is because all dynamics going to transformed number 1 will consist of multiple reduced dynamics, in which transformed number is less than the corresponding starting number instead of 1.We also present an induction method for Collatz Conjecture for better understanding of Reduced Collatz Conjecture and reduced version of the induction that is easier to tackle.We denoted reduced dynamics asCODE(x) (called code) and explore some fundamental properties of it, especially the structure of reduced dynamics (i.e., unified format concatenated by regular segments).The starting numbers and their codes whose lengths are no more than 7 (i.e.,{(x,c)∣c=CODE(x),c≤7}) are also given and proved; thus, portion of x∈[3]4 has already guaranteed Reduced Collatz Conjecture. That is, x∈[3]16∪[11,23]32∪[7,15,59]128⇒∃CODE(x)). (Recall that codes for x∈[1]4 and x∈[0]2 are trivial - CODE(x∈[1]4)=IO and CODE(x∈[0]2)=O.)The future work for the proof of Collatz Conjecture can follow this direction, to just prove thatCODE(x) exists for the left portion of x∈[3]4. Indeed, we also discovered the bound between the counts of I and the counts of O for any valid code is related to log23, the period T in terms of CODE(x+T)=CODE(x) is related to the length of CODE(x), and how to compute residue class of x directly when CODE(x) is given, which will be presented in our other papers.



---

*Source: 6129836-2019-05-02.xml*