# A Reduced Collatz Dynamics Maps to a Residue Class, and Its Count ofx/2 over the Count of 3∗x+1 Is Larger than ln3/ln2

Authors: Wei Ren
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

We propose reduced Collatz conjecture and prove that it is equivalent to Collatz conjecture but more primitive due to reduced dynamics. We study reduced dynamics (that consists of occurred computations from any starting integer to the first integer less than it) because it is the component of original dynamics (from any starting integer to 1). Reduced dynamics is denoted as a sequence of “I” that represents (3∗x+1)/2 and “O” that represents x/2. Here, 3∗x+1 and x/2 are combined together because 3∗x+1 is always even and thus followed by x/2. We discover and prove two key properties on reduced dynamics: (1) Reduced dynamics is invertible. That is, given reduced dynamics, a residue class that presents such reduced dynamics can be computed directly by our derived formula. (2) Reduced dynamics can be constructed algorithmically, instead of by computing concrete 3∗x+1 and x/2 step by step. We discover the sufficient and necessary condition that guarantees a sequence consisting of “I” and “O” to be a reduced dynamics. Counting from the beginning of a sequence, if and only if the count of x/2 over the count of 3∗x+1 is larger than ln3/ln2, reduced dynamics will be obtained (i.e., current integer will be less than starting integer).


---

## Body

## 1. Introduction

The Collatz 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 current known integers that have been verified are about 60 bits by Silva using normal personal computers [1, 2]. They verified all integers that are less than 60 bits.Ren et al. [3] verified that 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. Ren [4] also pointed out a new approach for the possible proof of Collatz conjecture. Ren [5] proposed to use a tree-based graph to observe two key inner properties in reduced Collatz dynamics: one is ratio of the count of x/2 over the count of 3∗x+1, and the other is partition (all positive integers are partitioned regularly corresponding to ongoing dynamics). Ren and Xiao [6] also proposed an automata method for fast computing Collatz dynamics. All source code and output data by computer programs in those related papers can be accessed in public repository [7].


## 2. Preliminaries

Notation 1.
(1)
ℕ∗: positive integers(2)
ℕ=ℕ∗∪0(3)
12=xx≡1mod2,x∈ℕ∗; 02=xx≡0mod2,x∈ℕ∗(4)
im=xx≡imodm,x∈ℕ∗,m≥2,m∈ℕ∗,0≤i≤m−1,i∈ℕProposition 1.
x/2 always follows after 3∗x+1.Proof.
Whenx∈12, then next computation is 3∗x+1. Obviously, 3∗x+1∈02; thus, the next computation must be x/2 consequently.
We thus can represent required computation as3∗x+1/2 and x/2, which are denoted by Ix and Ox, respectively.Notation 2.
Ix=3∗x+1/2, Ox=x/2.
Note thatIx and Ox can be simply denoted as I⋅ and O⋅, or I and O, respectively. Obviously, ∀x∈ℕ∗, Ix=3∗x+1/2>x, and Ox=x/2<x. That is, the reason of notation, I, represents “Increase” and, O, represents “dOwn.”Definition 1.
Collatz transformation, denoted asf⋅, where f⋅=I⋅=3∗x+1/2 if x∈12, and f⋅=O⋅=x/2 if x∈02.Remark 1.
(1)
We assumef0x=x.(2)
Obviously,f1f2…fnx=fnfn−1…f2f1x, where fi⋅∈I⋅,O⋅, i=1,2,…,n, and “” is concatenation of Collatz transformations. For simplicity, we just denote fi⋅ as f∈I,O.(3)
fnx=f…f︸nx, fnx=ffn−1x,n∈ℕ∗. Note that whether f is I or O in ffn−1x, is determined by fn−1x∈12 or 02.Definition 2.
(Collatz conjecture).∀x∈ℕ∗ and ∃L∈ℕ∗, such that fLx=1, where f∈I,O.
Obviously, Collatz conjecture is held whenx=1. In the following, we mainly concern x≥2,x∈ℕ∗.Definition 3.
(reduced Collatz conjecture).∀x∈ℕ∗,x≥2, and ∃L∈ℕ∗, such that fLx<x and fix<x, i=0,1,…,L−1, f∈I,O.
Obviously,L must be the minimal positive integer such that fLx<x.Theorem 1.
Collatz conjecture is equivalent to reduced Collatz conjecture.Proof.
∀x,L∈ℕ∗,x≥2, it is obvious that fLx∈ℕ∗, i.e., fLx≥1.(1)
Suppose Collatz conjecture is true. That is,∀x∈ℕ∗,x≥2, ∃L∈ℕ∗, fLx=1. Thus, fLx<x. Hence, reduced Collatz conjecture is true.(2)
Inversely, suppose reduced Collatz conjecture is true. That is,∀x∈ℕ∗,x≥2, ∃q0∈ℕ∗, fq0x<x.
Iffq0x=1, then Collatz conjecture is true.
Iffq0x>1, then let y1=fq0x. As reduced Collatz conjecture is true, ∃q1∈ℕ∗, fq1y1<y1.
For better notation, lety0=x. Iteratively, if yi=fqi−1yi−1=1,i∈ℕ∗, then Collatz conjecture is true. If yi=fqi−1yi−1>1, then ∃qi∈ℕ∗, yi+1=fqiyi<yi.
Thus,yi+1<yi<⋯<y1<y0=x. yii∈ℕ∗ is a strictly decreasing sequence.
Besides,yi+1=fq0+q1+q2+⋯+qix≥1.
Therefore, after finite times of iterations,∃n∈ℕ∗, yn=1.
That is,∃q=q0+q1+⋯+qn−1=∑i=0n−1qi, q∈ℕ∗, fqx=1.
Thus, Collatz conjecture is true.Remark 2.
(1)
We call an ordered sequencefq∈I,Oq in the above proof as original dynamics (referring to fqx=1), which consists of q occurred Collatz transformations during the computing procedure from a starting integer to 1. For example, the original dynamics of 5 is IOOO due to 5⟶16⟶8⟶4⟶2⟶1.(2)
In contrast, we callfq0 in the above proof as reduced dynamics (referring to fq0x<x), which is represented by a sequence of occurred Collatz transformations during the computing procedure from a starting integer (i.e., x) to the first transformed integer that is less than the starting integer (i.e., fq0x). For example, the reduced dynamics of 5 is IO due to 5⟶16⟶8⟶4.(3)
Obviously, reduced dynamics is more primitive than original dynamics because original dynamics consists of reduced dynamics. Simply speaking, reduced dynamics are building blocks of original dynamics.
Due to above theorem, we concentrate on reduced dynamics.Notation 3.
(RDx). It denotes reduced dynamics of x that are represented by f∈I,O. Formally, ∀x∈ℕ∗, x≥2, if ∃L∈ℕ∗ such that fLx<x and fix<x,i=0,1,…,L−1, where f∈I,O; then, let s=fL∈I,OL and s is called as reduced dynamics of x, denoted as RDx=fL=s.Remark 3.
(1)
Simply speaking (or recall that),RDx represents occurred Collatz transformations in terms of I and O during the computing process from starting integer x to the first transformed integer that is less than x.(2)
Recall that,fL∈I,OL is an ordered sequence consisting of I and O. Besides, fL=fL−1f, fLx=ffL−1x, and f0x=x. Furthermore, this sequence implicitly matches the parity of all occurred intermediate transformed integers that are taken as input of f⋅.(3)
Roughly speaking, inRDx=fL, x is called the starting integer. fix,i=1,2,…,L are called transformed integers. fLx is the first transformed integer that is less than the starting integer x. In other words, fix<x,i=0,1,…,L−1, and fLx<x. (f0x=x). Besides, the parity of fix determines the selection of the intermediately next f∈I,O after fi.(4)
Obviously,RDx∈02=O.(5)
For example,RD3=IIOO, RD5=IO, RD7=IIIOIOO, RD9=IO, and RD11=IIOIO. Indeed, we design computer programs that output all RDx,∀x∈1,99999999 [7]. From the data we discover the property—period and its relation to the number of computing x/2 in reduced dynamics—which will be proved in the remainder of this paper.(6)
In fact, we proved some results onRDx for specific x, e.g., RDx∈14=IO, RDx∈316=IIOO, and RDx∈1132=IIOIO [5].(7)
IIOO can be denoted in short as I2O2. IIIOIOO can be denoted in short as I3OIO2. In other words, we denote I…I︸n as In, and we denote O…O︸n as On, where n∈ℕ∗,n≥2. We also assume I1=I and O1=O. I0=O0=∅ means no transformation occurs.(8)
We will formally prove that the ratio exists in any reduced Collatz dynamics. That is, the count ofx/2 over the count of 3∗x+1 is larger than log23 in this paper. The ratio can also be observed and verified in my proposed tree-based graph [5].Example 1.
RD5=IO, if and only if(1)
“I” is due to 5∈12(2)
I5=3∗5+1/2=8<5, and thus it continues(3)
“O” is due to I5=8∈02(4)
IO5=OI5=O8=8/2=4<5, and thus it ends
To better present above the implicity in reduced dynamics, we introduce two functions as follows.Definition 4.
Is Matched:x×c⟶bool. It takes input x∈ℕ∗ and c∈I,O, and outputs bool∈True,False. If x∈12 and c=I, or if x∈02 and c=O, then output bool=True. Otherwise, output bool=False.Remark 4.
Simply speaking, this function checks whether the forthcoming Collatz transformation (i.e.,c∈I,O) matches with the current transformed integer x.Definition 5.
GetS:s×i×j⟶s′. It takes input s,i,andj, where s∈I,Os, 1≤i≤s, and 1≤j≤s−i−1, and outputs s′, where s=sas′sb, sa=i−1, s′=j, and sb=s−sa−s′, and “⋅” returns length in terms of the total count of I or O.Remark 5.
(1)
For example,GetSIIOO,1,4=IIOOand GetSIIOO,1,3=IIO.(2)
Especially,GetSs,1,s=s. GetSs,s,1 returns the last transformation in s. GetSs,1,1 returns the first transformation in s. GetSs,j,1 returns the jth transformation in s.(3)
In other words,s′ is a selected segment in s that starts from the location i and has the length of j. Indeed, that is, the reason we call this function as “Get Substring.”(4)
Simply speaking, this function can obtain the Collatz transforms fromi to i+j−1 from a given inputting transform sequence (e.g., reduced dynamics) in terms of s∈I,Os.(5)
Note thatGetS⋅ itself is a function. In other words, it can be looked as GetS⋅⋅.For example, GetSIIOO,1,13=I3=3∗3+1/2=5, GetSIIOO,1,23=II3=II3=I5=3∗5+1/2=8, GetSIIOO,1,33=IIO3=OII3=O8=8/2=4, and GetSIIOO,1,43=IIOO3=OIIO3=O4=4/2=2<3.(6)
It is worth to stress that, although in the above definitionj≥1, it can be extended to j≥0 by assuming GetS⋅,⋅,0x=x.Proposition 2.
Supposex∈ℕ∗,x≥2. If RDx exists, then(1)
sx<x, where s=RDx(2)
GetSs,1,ix<x, where i=1,2,…,s−1(3)
Is MatchedGetSs,1,j−1x,GetSs,j,1=True, where j=1,2,…,sProof.
Straightforward by the definition ofRDx.Remark 6.
(1)
sx is the last transformed integer, or the first transformed integer that is less than the starting integer.(2)
GetSs,1,ix (i=1,2,…,s−1) are all intermediate transformed integers.(3)
Whenj=1, GetSs,1,j−1x=GetSs,1,0x=x. GetSs,j,1 is the first transformation.(4)
IfGetSs,1,j−1x (j=2,…,s) is the current transformed integer; then, GetSs,j,1 is the next intermediate Collatz transformation.Proposition 3.
∀x∈ℕ∗, x≥2, if RDx exists; then, RDx is unique.Proof.
Straightforward. Givenx, either Ix or Ox is deterministic and unique. Similarly, given x, s′x is deterministic and unique, where s′=GetSs,1,i,s=RDx,i=1,2,…,s. Thus, s is unique for any given x.Remark 7.
We assumeRDx=1=IO, although IO1=O3∗1+1/2=O2=2/2=1<x. In other words, we assume the reduced dynamics of x=1 is IO. In the following, we always concern x≥2,x∈ℕ∗.Proposition 4.
Givenx∈ℕ∗, if RDx exists, then RDx ends by O.Proof.
Straightforward due toIx=3∗x+1/2>x. Suppose ∃x∈ℕ∗, x≥2, sx<x, and RDx=sI. Then, sIx=Isx>sx; thus, RDx=sIx<x. Contradiction occurs.Proposition 5.
RDx∈02=O and RDx∈14=IO.Proof.
(1)
x∈02, thus O occurs. x/2<x, thus RDx=O.(2)
Ifx=1, RD1=IO (by assumption).
Ifx≥2, x=4t+1∈12, where t∈ℕ∗. Thus, I occurs. Ix=3∗x+1/2=3∗4t+1+1/2=12t+4/2=2∗3t+1∈02. 2∗3t+1>x=4t+1, thus further transformation occurs. OIx=2∗3t+1/2=3t+1<4t+1=x∵t∈ℕ∗, thus RDx=IO.Proposition 6.
Givenx∈34, if RDx exists, then RDx∈IpOI,O≥1, p≥2.Proof.
Letx=4t+3, t∈ℕ. Obviously, x∈12. Ix=3x+1/2=12t+10/2=6t+5∈12. I2x=IIx=36t+5+1/2=9t+8.(1)
Ift∈02∪0, then 9t+8∈02. Thus, the next transformation is “x/2.” Thus, current occurred transformations are “IIO.” Besides, IIOx=9t+8/2=4.5t+4>4t+3=x. Further transformation thus occurs. Hence, if RDx exists, then RDx∈I2OI,O≥1.(2)
Ift∈12, then 9t+8∈12. Thus, current occurred transformations are “III.” Besides, IIIx=39t+8+1/2=27t+25/2=13.5t+12.5>4t+3=x. Further transformation occurs. Hence, if RDx exists, then RDx∈I3I,O≥1.
IfIIIx∈12, then more “I” occurs. Obviously, IIIIx>x. Further transformation occurs. Hence, if RDx exists, then RDx∈I4I,O≥1. If IIIx∈02, then IIIOx=13.5t+12.5/2=6.75t+6.25>4t+3=x. Further transformation occurs consequently. Hence, if RDx exists, then RDx∈I3OI,O≥1.
SupposeRDx=fL∈I,OL. There exists at least one “O” in L transformations, otherwise fLx=ILx>IL−1x>⋯>Ix>x, which contradicts with fLx<x. Besides, IpOx=Ipx/2>Ip−1x/2=Ip−1Ox>⋯>IIOx>x, p≥3; thus, there exists further transformation after IpOp≥3.
In summary, ifRDx∈34 exists, then RDx∈IpOI,O≥1,p≥2.Theorem 2 (format theorem).
Givenx∈ℕ∗, if RDx exists, then RDx∈IpOI,Oq, where p∈ℕ and q=RDx−p−1. Besides,(1)p=0,x∈02,1,x∈14,2,x∈38,α+2t+1=2α∗A,A∈12,α∈N∗x∈78.
q=0 when p=0,1; q≥1 when p≥2.Proof.
The range ofq is straightforward due to Propositions 5 and 6; thus, we mainly concern p.
By Proposition5, if x∈02, then RDx=O and p=0. If x∈14, then RDx=IO and p=1.
Next, we concentrate onx∈34.
RD3=IIOO=I2O2, which can be manually and easily verified.
Letx=4t+3,t∈ℕ∗.(1)
Case I:t∈02.Asx=4t+3∈12, I⋅ is conducted consequently. As Ix=3x+1/2=1.5x+1.5>x and IIx>Ix>x, the checking on whether the current transformed number is less than the starting number may be omitted in some straightforward cases.Ix=3x+1/2=34t+3+1/2=12t+10/2=6t+5∈12; thus, transformation I⋅ is conducted consequently.IIx=IIx=36t+5+1/2=18t+16/2=9t+8∈02. Thus, O⋅ is conducted consequently.OIIx=IIOx=9t+8/2=4.5t+4>4t+3. Thus, further transformation is conducted consequently.Therefore,RDx∈I2OI,O≥1.(2)
Case II:t∈12.Asx=4t+3∈12, I⋅ is conducted consequently.Ix=3x+1/2=34t+3+1/2=12t+10/2=6t+5∈12; thus, I⋅ is conducted consequently.IIx=36t+5+1/2=18t+16/2=9t+8∈12. Thus, I⋅ is conducted consequently.IIIx=39t+8+1/2=27t+25/2. It depends on the partition of t (more specifically, t∈14 or 34) whether 27t+25/2 is even or odd.(2.1)
Ift∈14, IIIx=27t+25/2=27∗4∗k+1+25/2=108k+52/2=54k+26∈02 (k∈ℕ∗); thus, O⋅ will occur consequently.(2.2)
Ift∈34, IIIx=27t+25/2=27∗4∗k+3+25/2=108k+106/2=54k+53∈12; thus, I⋅ will occur consequently.IIIOx=27t+25/2/2=54k+26/2=27k+13, whose parity depends on the parity of k.IIIIx=327t+25/2+1/2=354k+53+1/2=162k+160/2=81k+80, whose parity depends on the parity of k.
In other words, the judgement on the parity ofIIIOx is undecidable, unless the domain (t∈14 or t∈34) is partitioned further.
For exploring more general results, we put it in another way as follows.
Suppose there exist at mostp times of “I” at head (i.e., IpO…) for x∈34. Observing the following equation for Ipx after consecutive p≥2 times of “I”,(2)Ipx=3…33x+1/2+1/2…+12=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∈ℕ=32p4t+3+1−1=3p2p−2t+1−1∈ℕ∗.
Note that the 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 3i/2i−2t+1−1∈12, where 2≤i≤p−1,i∈ℕ∗.(ii)
Besides,3i/2i−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 the current transformed number be in 02. Thus, we need to explore the requirement on p for given t such that(3)3i2i−2t+1−1∈12,2≤i≤p−1,3i2i−2t+1−1∈02,i=p.
Representt+1 as 2α∗A,A∈12,α∈ℕ∗. That is, t+1=2α∗A. Obviously, this representation is unique. We thus need to prove that the requirement in equation (3) 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∈ℕ∗, we have α+2−i>0:(4)3i2i−2t+1−1=3i2i−2∗2α∗A−1=3i∗2α−i+2∗A−1.
α+2−i>0⟹2α−i+2∈02⟹3i∗2α−i+2∗A∈02⟹3i∗2α−i+2∗A−1∈12.
Wheni=p=α+2, we have exactly(5)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 the requirement in equation (3), as desired.Corollary 1(t determines p corollary).
Given starting integerx∈34 (i.e., x=4t+3,t∈ℕ), the count of consecutive “I” (denoted as p) is determined by t as follows.
Ift∈02, then p=2; if t∈12, then p=α+2, where α=log2t+1/A∈ℕ∗, and A=maxaa∈12,at+1.Proof.
It is straightforward by Theorem2.Corollary 2.
Given the starting integerx∈34,t=x−3/4∈ℕ, the first p count of Collatz transformations must be Ip and p can be determined by t, and the transformed integer after Ip transformations is(6)Ipx=32px+1−1=3p2p−2t+1−1∈ℕ∗,p≥2.Proof.
It is straightforward by Theorem2 and Corollary 1.Remark 8.
(1)
Note that, due to Corollary1, p for Ip in RDx can be computed by t=x−3/4 and log2t+1/A directly without conducting concrete Collatz transformations, which can shorten the computation delay for reduced dynamics.(2)
Besides, by equation (2) or Corollary 2, if t=0, we then have p=2 because Ipx=3p/2p−2t+1−1=3p/2p−2−1∈ℕ∗, which matches with the result RD3=IIOO by manually computing.(3)
Indeed, equation (2) can be extended to include all cases (i.e., for p=0,1). If p=0, by assuming I0x=x, I0x=x=3/20x+1−1=3/2px+1−1. If p=1, I1x=Ix=3∗x+1/2=3/21x+1−1=3/2px+1−1. Therefore, Ipx=3/2px+1−1 for p∈ℕ∗.Corollary 3.
Supposex=2n−1,n∈ℕ∗. If RDx exists, then RDx∈InOI,O≥0.Proof.
Straightforward.Remark 9.
Simply speaking, above corollary states that ifRDx=2n−1,n∈ℕ∗ exists, then the first n+1 Collatz transformations for x must be InO. Indeed, the resumption on the existence of the reduced dynamics of x can be omitted. That is, the first n+1 Collatz transformations in original dynamics of x must also be InO.Example 2.
RD7=IIIOIOO=I3OIOO, as 7⟶22⟶11⟶34⟶17⟶52⟶26⟶13⟶40⟶20⟶10⟶5<7.
Next, corollary states that reduced dynamics consists of segment or segments with a unified form asIpOq,p≥1andq≥1.Corollary 4.
Givenx∈34, if RDx exists, then(7)RDx∈Ip0≥2Oq0≥1Ip1≥1Oq1≥1…Ipn≥1Oqn≥1.Proof (straightforward).
x∈12, thus I occurs. After p times of I transformations, Ipx∈02 and thus O follows. After q times of O transformations, IpOqx∈12, thus I occurs. Indeed, q can be determined by Ipx by q=log2Ipx/B, B=maxbb∈12,bIpx.
Iteratively, each segment has a unified formIpOq, where p,q∈ℕ∗.
The first segment is listed solely because the distinction between the first segment and the other segments is thatp0≥2 but pi≥1,i∈ℕ∗ (in other words, when and only when an intermediate transformed number is in 14, pi=1. Otherwise, pi≥2).


## 3. Derivex from RDx

### 3.1. Preparation

Notation 4.
SetRD=sx∈ℕ∗,∃RDx,s=RDx,s∈I,O≥1.
That is,∀x∈ℕ∗, if RDx exists, then RDx=s will be included in SetRD, which is a set of existing reduced dynamics.
In this section, we will study two problems as follows:(1)
Inverse problem: given s∈SetRD, is it possible to derive starting integer x such that RDx=s?(2)
What is thesufficient and necessary conditions for any existing reduced dynamics, that is, given s∈I,O≥1, how to decide whether s∈SetRD?
Before exploring general situations, we give two trivial cases.Proposition 7.
O∈SetRD and IO∈SetRD.Proof (straightforward).
RDx∈02=O and RDx∈14=IO by Proposition 5.
In the following, we thus mainly concentrate onx∈34, where their reduced dynamics presents the form such as Ip≥2OI,Oq≥1,p,q∈ℕ∗ once it exists (recall Proposition 6).Theorem 3 (subset theorem).
Supposes∈SetRD, s≥2, x∈ℕ∗, i=0,1,…,s−2. We have(1.1)xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈02(1.2)xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈02(2.1)xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈12(2.2)xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈12Proof.
Wheni=0, there exists two and only two cases as follows:(1)
IfGetSs,i+1,1=O, then GetSs,1,ix∈02. There exists two subcases as follows:(1.1) IfGetSs,i+2,1=I, then OGetSs,1,ix∈12⟹GetSs,1,ix/2∈12⟹GetSs,1,ix∈24⊂02. Thus, xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈02.(1.2) IfGetSs,i+2,1=O, then OGetSs,1,ix∈02⟹GetSs,1,ix/2∈02⟹GetSs,1,ix∈04⊂02. Thus, xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈02.(2)
IfGetSs,i+1,1=I, then GetSs,1,ix∈12. There exist two subcases as follows:(2.1) IfGetSs,i+2,1=I, then IGetSs,1,ix∈12⟹3∗GetSs,1,ix+1/2∈12⟹3∗GetSs,1,ix+1∈24⟹3∗GetSs,1,ix∈14⟹GetSs,1,ix∈34⊂12. Thus, xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈12.(2.2) IfGetSs,i+2,1=O, then IGetSs,1,ix∈02⟹3∗GetSs,1,ix+1/2∈02⟹3∗GetSs,1,ix+1∈04⟹3∗GetSs,1,ix∈34⟹GetSs,1,ix∈14⊂12. Thus, xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈12.
We can prove similarly fori=1,2,…,s−2.Corollary 5.
Supposes∈SetRD, s≥2, i=0,1,…,s−2, x∈ℕ∗. We have(1.1)xGetSs,1,i+1x∈12=xGetSs,1,ix∈24(1.2)xGetSs,1,i+1x∈02=xGetSs,1,ix∈04(2.1)xGetSs,1,i+1x∈12=xGetSs,1,ix∈34;(2.2)xGetSs,1,i+1x∈02=xGetSs,1,ix∈14Proof.
Straightforward by Theorem3.Remark 10.
(1)
Corollary5 states that the residue classes are partitioned regularly into halves and either half will present either next intermediate transformation in terms of I or O (indeed, the partition property is thoroughly explored and proved in my other paper [8]. Note that this paper is independent from the cited paper.)(2)
Note that Theorem3 is not only guaranteed for reduced dynamics but also for original dynamics.Corollary 6.
Supposes∈SetRD, s≥2, i=2,3,…,s, x∈ℕ∗. We have(8)xIs MatchedGetSs,1,i−1x,GetSs,i,1=True⊂xIs MatchedGetSs,1,i−2x,GetSs,i−1,1=True.Proof.
Straightforward by Theorem3.
Roughly speaking, above corollary asserts that the last parity requirement is sufficient to guarantee all previous parity requirements. That is, the residue equation for last parity requirement is sufficient for deriving the required residue class for satisfying all parity requirements.
In the following, notationim is extended in which i could be larger than m or less than 0. That is, im=xx=k∗m+i,k∈ℕ,i∈ℤ,m∈ℕ∗,m≥2. ℤ is the integer.Lemma 1.
a∈ℕ,x,b,c∈ℕ∗,b≥2, thus(1)
x+c∈ab⟺x∈a−cb(2)
c∗x∈ab⟺x∈c−1∗ab, if gcdc,b=1(3)
x/c∈ab⟺x∈a∗cb∗cProof.
(1)x+c∈ab⟺x+c=k∗b+a,k∈ℕ⟺x=k∗b+a−c⟺x∈a−cb.
(2)(9)c∗x∈ab⟺c∗x=k∗b+a,k∈ℕ⟺k′∗b+cb∗x=k∗b+a,∵c=k′∗b+cb,k′∈ℕ⟺cb∗x=k−k′∗x∗b+a⟺cb∗x∈ab⟺c−1b∗cb∗x∈c−1b∗ab∵gcdc,b=1,∃c−1b,s.t.c−1b∗cb=1b⟺x∈c−1∗ab.
(3)x/c∈ab⟺x/c=k∗b+a,k∈ℕ⟺x=k∗b∗c+a∗c,k∈ℕ⟺x∈a∗cb∗c.
Indeed, ifgcdc,b=1, then c−1b exists and is the inverse of cb in group ℤ/bℤ∗=ℤ/bℤ∖0,∗modb such that c−1b∗cb=1b.


### 3.2. Derivex if RDx = IpOq

In this section, we assumep,q∈ℕ∗,p≥2, x∈34 if no explicitly declaration exists.Lemma 2.
Supposep,q∈ℕ∗,p≥2.
∃x∈34 such that RDx=IpOq, if and only ifReq-I):Ipx∈02qReq-II):IpOqx<x∧IpOq−1x<xProof.
By Theorem3 or Corollary 6, all parity sequence can be guaranteed if the last parity requirement is guaranteed.
IpOq−1x∈02⟺Ipx/2q−1∈02⟺Ipx∈02q, by Lemma 1 (3).
Thus, Req-I is sufficient for the requirements for all parities.
Anyx such that IpOq−1x<x can guarantee IpOix>x,i=1,2,…,q−2, because IpOix=IpOq−1x∗2q−1−i. Besides, Iix>x,i=1,2,…,p, due to Ix=3∗x+1/2>x. Thus, Req-II is sufficient for the requirements for all transformed integers.
Next, we check the requirement for Req-I.Lemma 3.
Ipx∈02q⟺x∈3p−1∗2p−12p+q.Proof.
Ipx∈02q
⟺3/2px+1−1∈02q∵ Equation (2)
⟺3/2px+1∈12q∵ Lemma 1(1)
⟺3px+1∈2p2p+q∵ Lemma 1(3)
⟺3p2p+qx+1∈2p2p+q∵ Lemma 1(2)
⟺x+1∈3p−1∗2p2p+q∵ Lemma 1(2) and gcd3p,2p+q=1⟺x∈3p−1∗2p−12p+q∵ Lemma 1 (1)
Indeed,3p−12p+q is the inverse of 3p2p+q in group ℤ/2p+qℤ∗=ℤ/2p+qℤ∖0,∗mod2p+q. Besides, even if p=1, the above lemma still holds due to Corollary 2 and Remark (3).
Next, we explore Req-II, assuming that Req-I is already guaranteed—x∈3p−1∗2p−12p+q.Notation 5.
λ=log21.5.Lemma 4.
IpOqx<x∧IpOq−1x≥x⟺q=λ∗p∧x>3p−2p/2p+q−3p.Proof.
(1)IpOqx<x⟺3/2px+1−1/2q<x∵ equation (2)(10)⟺3px+3p<2qx+12p⟺3px+3p<2p+qx+2p⟺3p−2p<2p+q−3px∵x>0,3p−2p>0⟺2p+q−3p>0∧x>3p−2p2p+q−3p.
(2)2p+q−3p>0⟺2q>3p/2p⟺q>log21.5∗p⟺q≥log21.5∗p, since q∈ℕ∗,log21.5∈ℚ,log21.5∗p∈ℕ∗.
(3)IpOqx<x∧IpOq−1x≥x⟺q=log21.5∗p, as q is the minimal one in q≥log21.5∗p.
Next theorem proves thatq=λ∗p is the necessary condition for IpOq∈SetRD.Theorem 4.
IfIpOq∈SetRD,p,q∈ℕ∗,p≥2, then(1)
∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq(2)
q=λ∗pProof.
It is straightforward due to Lemmas2–4.
Next theorem proves thatq=λ∗p is also the sufficient condition for IpOq∈SetRD.Theorem 5.
Ifq=λ∗p, p,q∈ℕ∗,p≥2, then(1)
∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq(2)
IpOq∈SetRDProof.
It is due to Lemmas2–4.
Next corollary claims sufficient and necessary condition forIpOq∈SetRDp≥2.Corollary 7.
q=λ∗p⟺IpOq∈SetRD, where p,q∈ℕ∗,p≥2.Proof.
It is straightforward by Theorems4 and 5.
Next corollary extends above corollary by tackling the casesp=0 and p=1.Corollary 8.
q=max1,λ∗p⟺IpOq∈SetRD, where p∈ℕ,q∈ℕ∗.Proof.
(1)p=0 and q=max1,0=1. I0O1=O∈SetRD, as RDx∈02=O.
(2)p=1 and q=max1,λ∗1=λ∗1=1. I1O1=IO∈SetRD, as RDx∈14=IO.
(3)p≥2 and q=max1,λ∗p=λ∗p. IpOq∈SetRD due to Corollary 7.
Inverse direction can be proved similarly.Corollary 9.
SetRD=+∞.Proof.
∀p∈ℕ∗,p≥2, let q=λ∗p. Thus, 2p+q>3p. ∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq. Hence, SetRD=+∞.


### 3.3. Derivex if RDx = Ip1Oq1Ip2Oq2…IpnOqn

In this section, we assumepi,qi∈ℕ∗, p1≥2, n≥2, and x∈34; if there exists no explicitly declaration.Lemma 5.
Supposes=Ip1Oq1Ip2Oq2…IpnOqn and kj=∑i=1jpi+qi, j=1,2,…,n−1.(1)
GetSs,1,kjx≥x⟹GetSs,1,kj−mx>x, m=1,2,…,qj(2)
GetSs,1,kjx≥x⟹GetSs,1,kj+mx>x, m=1,2,…,pj+1Proof.
Straightforward.(1)
BecauseGetSs,1,kjx≥x and GetSs,1,kj−mx=GetSs,1,kjx∗2m>GetSs,1,kjx, we have GetSs,1,kj−mx>x, m=1,2,…,qj(2)
BecauseGetSs,1,kjx≥x and GetSs,1,kj+mx=ImGetSs,1,kjx>GetSs,1,kjx (due to Ix>x), we have GetSs,1,kj+mx>x, m=1,2,…,pj+1Remark 11.
For better understanding the above lemma, we can explain the conclusion as follows: if “going Down” stage ends with a transformed integer that is not less than the starting integer, then all transformed integers in its “left” and “right” will be larger than the starting integer.Lemma 6.
Supposepi,qi∈ℕ∗,p1≥2,n≥2.
∃x∈34 such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, if and only ifReq-I):Ip1Oq1Ip2Oq2…Ipnx∈02qnReq-II):Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥xReq-III):Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1Proof.
Roughly speaking, Req-I is a residue equation to specify the requirement for parity sequence, and Req-II and Req-III are two inequalities to specify the requirements for transformed integers.(1)
Req-I is sufficient and necessary because of Theorem3.(2)
Req-II.Ip1Oq1Ip2Oq2…IpnOix=Ip1Oq1Ip2Oq2…IpnOqn−1x∗2qn−1−i. Thus,(11)Ip1Oq1Ip2Oq2…IpnOqn−1x≥x⟹Ip1Oq1Ip2Oq2…IpnOix>x,i=1,2,…,qn−2.Together withIp1Oq1Ip2Oq2…IpnOqnx<x, qn is thus the minimal one to let Ip1Oq1Ip2Oq2…IpnOix<x.(3)
Req-III. Obviously,Iix>x,i=1,2,…,p1. Besides, let s=RDx. By Lemma 5, we have(12)GetSs,1,∑i=1jpi+qix≥x,j=1,2,…,n−1⟹GetSs,1,kx>x,k=p1+1,p1+2,…,∑i=1n−1pi+qi+pn.Lemma 7.
Ip1Oq1Ip2Oq2…Ipnx∈02qn,n,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n,⟺x∈−∑i=1nAiBiCi−1Cn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, and Ci=2∑j=1ipj+qj,C0=1.The proof is somewhat straightforward but the computation is tedious; we thus move them to Appendix (Section4.1).Remark 12.
(1)
The conclusion forn=1 is identical with that in Theorem 5.(2)
Whenp1=q1=1, the conclusion 3−p12p1−12p1+q1=3−1∗2−14=3∗2−14=14, which is identical with that in Proposition 7. Thus, p1≥2 in Lemma 7 can be extended to p1≥1.
Next lemma is stated only forx∈−∑i=1nAiBiCi−1Cn, since Req-I should be guaranteed for ordered parity sequence firstly.Lemma 8.
Ip1Oq1Ip2Oq2…IpnOqnx<x,n,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n⟺x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0.Proof.
(13)Ip1Oq1Ip2Oq2…IpnOqnx<x⟺∏i=1naix+∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn<x,(due to the equation in the proof of Lemma 7 (7)) ⟺1−∏i=1naix>Ψ
whereΨ=∏i=2naib1+∏i=2naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn(14)⟺1−∏i=1n3pi2pi+qi∗x>Ψ⟺1−3∑i=1npi2∑i=1npi+qi∗x>Ψ⟺x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0,∵x>0,Ψ>0.
Indeed,(15)Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+anbn−1+bn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+3pn2pn+qn3pn−1−2pn−12pn−1+qn−1+3pn−2pn2pn+qn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+3pn−1−2pn−13pn2pn+qn+pn−1+qn−1+3pn−2pn2pn+qn.Remark 13.
(1)
Whenn=1, Ψ=3pn−2pn/2pn+qn=3p1−2p1/2p1+q1:(16)Ip1Oq1x<x⟺x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0⟺x>Ψ∗2p1+q12p1+q1−3p1∧2p1+q1−3p1>0⟺x>3p1−2p12p1+q1∗2p1+q12p1+q1−3p1∧2p1+q1−3p1>0⟺x>3p1−2p12p1+q1−3p1∧2p1+q1−3p1>0,which is exactly identical with that of Theorem5. Therefore, the conclusion can be extended to n=1.(2)
Whenn=1 with p1=1,q1=1. x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi=3p1−2p1/2p1+q1−3p1=3−2/22−31=1/1=1. It is consistent with the conclusion in Proposition 7 for RDx∈14=IO.
Note that, here,2∑inpi+qi−3∑inpi>0 is a necessary condition for Ip1Oq1Ip2Oq2…IpnOqnx<x.
Next, we check the requirement Req-III. Again, the next lemma is discussed only forx∈−∑i=1nAiBiCi−1Cn, since Req-I should be guaranteed for designated parity sequence as a prerequisite.Lemma 9.
Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1,n≥2⟺2∑ijpi+qi−3∑ijpi<0.Proof.
Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1(17)⟺∏i=1jaix+∏i=2jaib1+∏i=3jaib2+⋯+∏i=j−1jaibj−2+∏i=jjaibj−1+bj≥x,(due to the equation in the proof of Lemma 7 (7)) ⟺1−∏i=1jaix≤Ψj
where(18)Ψj=∏i=2jaib1+∏i=3jaib2+⋯+∏i=j−1jaibj−2+∏i=jnaibj−1+bj⟺1−∏i=1j3pi2pi+qi∗x≤Ψj⟺1−3∑i=1jpi2∑i=1jpi+qi∗x≤Ψj⟺x≤Ψj∗2∑i=1jpi+qi2∑i=1jpi+qi−3∑i=1jpi∧2∑ijpi+qi−3∑ijpi>0∨2∑ijpi+qi−3∑ijpi<0.
Next, we will prove that2∑ijpi+qi−3∑ijpi>0,j=1,2,…,n−1 is impossible by contradiction.
SupposeIp1Oq1Ip2Oq2…Ipjx∈02qj⟺x∈Sj,j=1,2,…,n. By Lemma 6 (1) or Theorem 3, Sj+1⊂Sj,j=n−1,n−2,…,1.
Suppose∃j∈1,n−1 such that 2∑ijpi+qi−3∑ijpi>0. Select the minimal one in them (thus, for 1≤k≤j−1, 2∑ikpi+qi−3∑ikpi<0). Because of the generality of n in qn in Lemma 8, we have Ip1Oq1Ip2Oq2…IpjOqjx<x, when x>Ψj′=Ψj∗2∑i=1jpi+qi/2∑i=1jpi+qi−3∑i=1jpi, j∈1,n−1.
LetΨn′=Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.
Therefore, ifx>maxΨj′,Ψn′ and x∈Sn, then Ip1Oq1Ip2Oq2…Ipjx∈02qj, Ip1Oq1Ip2Oq2…IpjOqjx<x, and Ip1Oq1Ip2Oq2…IpkOqkx≥x,k=1,2,…,j−1. Thus, RDx∈Sn=Ip1Oq1Ip2Oq2…IpjOqj, which contradicts with RDx∈Sn=Ip1Oq1Ip2Oq2…IpnOqn in assumption. Thus, ∄j∈1,n−1,2∑ijpi+qi−3∑ijpi>0. That is, 2∑ijpi+qi−3∑ijpi<0,j=1,2,…,n−1.Lemma 10.
2∑inpi+qi−3∑inpi>0⟺∑i=1nqi≥λ∗∑i=1npi.Proof.
LetU=∑inpi,D=∑inpi+qi:(19)2∑inpi+qi−3∑inpi>0⟺2D>3U⟺D>log23∗U⟺D≥log23∗U,∵U,D∈ℕ∗,log23∈ℚ∗,log23∗U∈ℕ∗⟺D−U≥log23∗U−U⟺D−U≥log23∗U−U⟺D−U≥log21.5∗U⟺∑i=1nqi≥λ∗∑i=1npi.Lemma 11.
2∑ijpi+qi−3∑inpi<0⟺∑i=1jqi≥λ∗∑i=1jpi,j=1,2,…,n−1.Proof.
LetU′=∑ijpi,D′=∑ijpi+qi:(20)2∑ijpi+qi−3∑ijpi<0⟺2D′<3U′⟺D′<log23∗U′⟺D′≤log23∗U′−1,∵U′,D′∈ℕ∗,log23∈ℚ∗,log23∗U′∈ℕ∗⟺D′−U′≤log23∗U′−U′−1⟺D′−U′≤log23∗U′−U′−1⟺D′−U′≤log21.5∗U′−1⟺∑i=1jqi<λ∗∑i=1jpi.Lemma 12.
Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x⟺qn=λ∗∑i=1npi−∑i=1n−1qi∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.Proof.
By Lemma10, ∑i=1nqi≥λ∗∑i=1npi.
Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x, thus qn is the minimal one. Therefore, qn=λ∗∑i=1npi−∑i=1n−1qi.Theorem 6.
IfIp1Oq1Ip2Oq2…IpnOqn∈SetRD, pi,qi∈ℕ∗,p1≥2, i=1,2,…,n, n∈ℕ∗,n≥2, then(1)
∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1, Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,bi=3pi−2pi/2pi+qi,i=1,2,…n(2)
∑i=1nqi=λ∗∑i=1npi∧∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1,n≥2Proof.
It is straightforward due to Lemmas7–12.
Next theorem proves that∑i=1nqi=λ∗∑i=1npi and ∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1,n≥2 is also the sufficient condition for Ip1Oq1Ip2Oq2…IpnOqn∈SetRD.Theorem 7.
If∑i=1nqi=λ∗∑i=1npi, ∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1, pi,qi∈ℕ∗,p1≥2. i=1,2,…,n, n∈ℕ∗,n≥2, then(1)
∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, and Ci=2∑j=1ipj+qj,C0=1; Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qiandbi=3pi−2pi/2pi+qi,i=1,2,…,n(2)
Ip1Oq1Ip2Oq2…IpnOqn∈SetRDProof.
By Lemma12,(21)∑i=1nqi=λ∗∑i=1npi∧x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi⟹Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x.
Together withx∈−∑i=1nAiBiCi−1Cn, we have Ip1Oq1Ip2Oq2…Ipnx∈02qn due to Lemma 7.
Besides,Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1 by Lemmas 9 and 11. Therefore, by Lemma 6, ∃x∈ℕ∗,RDx=Ip1Oq1Ip2Oq2…IpnOqn.
Note that the above theorem indeed implies thatRDx=RDx+P=Ip1Oq1Ip2Oq2…IpnOqn, where P=2p1+q1+p2+q2+⋯+pn+qn=2∑i=1npi+qi=2RDx when x is sufficient large (i.e., x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi).
Indeed, the requirement for being sufficient large can be omitted and proved by us in another paper [9]. Note that this paper is independent with cited paper.
Following corollary states the necessary and sufficient condition for guaranteeing that anyIp1Oq1Ip2Oq2…IpnOqn, where pi,qi∈ℕ∗,p1≥2 and i=1,2,…,n,n∈ℕ∗,n≥2, is a reduced dynamics of some x∈ℕ∗.Corollary 10.
∑i=1nqi=λ∗∑i=1npi,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n,n∈ℕ∗,n≥2∧∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1⟺Ip1Oq1Ip2Oq2…IpnOqn∈SetRD.Proof.
Straightforward due to Theorems6 and 7.Theorem 8 (prefix-free theorem).
Supposepi,qi∈ℕ∗,i=1,2,…,n, p1≥2,n≥2. If s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, then GetSs,1,∑i=1jpi+qi∈SetRD,j=1,2,…,n−1.Proof.
Ip1Oq1Ip2Oq2…IpnOqn∈SetRD
⟹∀x∈−∑i=1nAiBiCi−1Cn,Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1
⟹2∑ijpi+qi−3∑ijpi<0,j=1,2,…,n−1∵ Lemma 9
⟹∄x∈ℕ∗,GetSs,1,∑i=1jpi+qix<x∵ Lemma 8
⟹GetSs,1,∑i=1jpi+qi∈SetRD,j=1,2,…,n−1.
Simply speaking, Theorem8 shows that SetRD is prefix-free. Regarding more general conclusion by including O or IO (i.e., for x∈34) and n=1 (i.e., for IpOq), we have following corollary.Corollary 11.
s∈SetRD⟹sI,O≥1⊂SetRD.Proof.
Straightforward.
Next, we give more general results by introducing two functions as follows:Definition 6.
FunctionCntI⋅. CntI:c⟶y takes as input c∈I,O≥1, and outputs y∈ℕ that is the count of “I” in c.Definition 7.
FunctionCntO⋅. CntO:c⟶y takes as input c∈I,O≥1, and outputs y∈ℕ∗ that is the count of “O” in c.
For example,CntIIIOO=2, CntOIIOO=2, CntIIIOIO=3, and CntOIIOIO=2.
Corollary 8 states thesufficient and necessary condition for s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, n≥2. It can be extended by using GetSs,1,k,k=1,2,…,s−1 instead of GetSs,1,∑i=1jpi+qi as follows.Corollary 12.
s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, pi,qi∈ℕ∗, p1≥2, i=1,2,…,n, n∈ℕ∗, n≥2, if and only if(1)
CntOs=λ∗CntIs(2)
CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1Proof.
Straightforward.
Ifn=1 and p=0,1 for IpOq are both included, the above corollary can be extended to the following corollary.Corollary 13.
s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, pi∈ℕ, qi∈ℕ∗, i=1,2,…,n,n∈ℕ∗, if and only if(1)
p1=0,n=1. s=O(2)
p1≥1. CntOs=λ∗CntIs, and CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1Proof.
(1)
It is trivials=O⟹s∈SetRD. Inversely, n=1,p1=0,s=Ip1Oq1=Oq1∈SetRD⟹s=O.(2)
n=1, s=Ip1Oq1,p1,q1∈ℕ∗.(2.1)p1=1. GetSs,1,1=I. Obviously, CntOGetSs,1,1=0<λ∗CntIGetSs,1,1=λ∗1=log21.5=1.s=IOq1, thus GetSs,1,2=IO. Then, CntOGetSs,1,2=1, λ∗CntIGetSs,1,2=λ∗1=1. Thus, s=2 and s=IO. Obviously, IO∈SetRD.Inversely,s=IO∈SetRD⟹CntOs=1=λ∗1=λ∗CntIs∧ (CntOGetSs,1,k=0<λ∗CntIGetSs,1,k=1,k=s−1=1).(2.2)p1≥2. q1=λ∗p1⟺Ip1Oq1∈SetRD by Corollary 7. Thus, q1=λ∗p1⟺CntOs=λ∗CntIs because CntOs=q1,CntIs=p1.Besides,q1=λ∗p1⟹CntOGetSs,1,k<λ∗CntIGetSs,1,k, k=1,2,…,s−1. The reason is as follows:Whenk=1,2,…,p1, CntOGetSs,1,k=0<λ∗CntIGetSs,1,k∈ℕ∗ is trivial.Whenk=p1+1,p1+2,…,p1+q1−1,q1=λ∗p1⟹CntOGetSs,1,k=k−p1≤q1−1<q1=λ∗p1=λ∗CntIGetSc,1,k as p1=CntIGetSs,1,k.(3)
n≥2. p1≥2. By Corollary 10, CntOc=λ∗CntIc∧CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1⟺s∈SetRD.
Next, we useCntO⋅ and CntI⋅ to restate sufficient and necessary condition for s∈SetRD as follows.Corollary 14 (form corollary).
s∈I,O≥1 is a reduced dynamics, if and only if(1)
s=1,s=O.(2)
s≥2,(22)CntOs=λ∗CntIs,CntOs′<λ∗CntIs′,s′=GetSs,1,i,i=1,2,…,s−1.Proof.
It is straightforward due toTheorem8 and Corollary 8–11.
Finally, we obtain the following inverse theorem as a summary.Theorem 9 (inverse theorem).
(1)
Ifs=1,s=O, then ∃x∈02 such that RDx=O(2)
Ifs≥2, s=Ip1Oq1Ip2Oq2…IpnOqn, pi,qi∈ℕ∗, i=1,2,…,n,n∈ℕ∗, CntOs=λ∗CntIs,CntOs′<λ∗CntIs′, s′=GetSs,1,k,k=1,2,…,s−1
Then,∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=s, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1, Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,bi=3pi−2pi/2pi+qi.Proof.
It is straightforward due to Theorem7 and form corollary (Corollary 12).
Following corollary states thatSetRD can be constructed by generating s∈I,O≥1 which satisfies requirements algorithmically instead of by conducting concrete Collatz transformations for enumerated starting integers.Corollary 15.
SetRD=O∪ss∈I,OL,L∈ℕ∗,L≥2,CntOs=λ∗CntIs,CntOs′<λ∗CntIs′,s′=GetSs,1,i,i=1,2,…,L−1.Proof.
It is straightforward due to Corollary12.
Following corollary states the relations betweenCntIs and CntOs+CntIs=s, s∈SetRD. Indeed, CntIs is the count of 3∗x+1/2 that equals the count of 3∗x+1 computation, and CntOs+CntIs equals the total count of x/2 computation in reduced dynamics.Corollary 16.
Ifs∈SetRD, then(1)
D≥log23∗U, where U=CntIs, D=s(2)
3U<2DProof.
(1) Whens=O, U=0, D=1. 1>log23∗0=0 by Corollary 13.
Whens≠O, s∈SetRD⟹D=CntOs+CntIs=log21.5∗CntIs+CntIs=log21.5∗U+U=log23∗U by Corollary 13.
In summary,s∈SetRD⟹D≥log23∗U, and note that “>” is obtained when and only whens=O.
(2)D≥log23∗U⟹D≥log23U⟹3U≤2D⟹3U<2D.Corollary 17.
s∈SetRD,s≥2⟹3CntIGetSs,1,i>2i, i=1,2,…,s−1.Proof.
Lets′=GetSs,1,i,i=1,2,…,s−1. Obviously, s′=i.
s∈SetRD⟹CntOs′<log21.5∗CntIs′∵ Corollary 12(23)⟹CntOs′<log21.5∗CntIs′,∵log21.5∈ℚ,CntIs,CntOs∈ℕ∗⟹CntOs′+CntIs′<log23∗CntIs′⟹s′<log23∗CntIs′⟹2s′<3CntIs′⟹3CntIGetSs,1,i>2i.Example 3.
By using the conclusion in fForm corollary (Corollary12), CntOs can be computed from CntIsdirectly as follows:(1)
s∈I,O≥1,s∈SetRD, CntIs=1⟹CntOs=λ∗CntIs=λ∗1=log21.5∗1=0.58496250∗1=1(2)
s∈I,O≥1,s∈SetRD, CntIs=2⟹CntOs=λ∗CntIs=λ∗2=log21.5∗2=0.58496250∗2=2(3)
s∈I,O≥1,s∈SetRD, CntIs=3⟹CntOs=λ∗CntIs=λ∗3=log21.5∗3=0.58496250∗3=2(4)
s∈I,O≥1,s∈SetRD, CntIs=4⟹CntOs=λ∗CntIs=λ∗4=log21.5∗4=0.58496250∗4=3
Due to inverse theorem (Theorem9), each s∈SetRD cannot map to more than one residue class with the module 2s. Thus, a function called Invrs can be defined as follows.Definition 8.
FunctionInvrs⋅. Invrs:s⟶rs takes input
s=O or(24)s=Ip1Oq1Ip2Oq2…IpnOqn∈I,O≥2,pi,qi∈ℕ∗,i=1,2,…,n,n∈ℕ∗CntOs=log21.5∗CntIs,CntOs′<log21.5∗CntIs′,s′=GetSs,1,k,k=1,2,…,s−1,and outputs r=02 when s=O, or(25)r=−∑i=1nAiBiCi−12c∩xx>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi,when s≥2, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,andbi=3pi−2pi/2pi+qi.
The following corollary states thatInvrs⋅ is injective. It is straightforward because the reduced dynamics of a starting integer is unique (Proposition 3).Corollary 18.
∀s1,s2∈SetRD,s1≠s2⟹r1≠r2, where r1=Invrss1 and r2=Invrss2.Proof.
It is straightforward by proving converse-negative proposition:(26)r1=r2⟹RDx∈r1=RDx∈r2⟹s1=s2.
IfInvrs⋅ is surjective, then Collatz conjecture will be true. That is, if ∪s∈SetRDInvrss=ℕ∗, then Collatz conjecture will be true. However, it is difficult to be proved because each residue class is partial due to the requirement of xx>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.
(Thanks to the period theorem that is proved in [9]; this requirement can be omitted. Besides, all the above conclusions, e.g., subset theorem (Theorem 3), prefix-free theorem (Theorem 8), form corollary (Corollary 12), and Inverse theorem (Theorem 9), can be observed in my proposed tree-based graph to present reduced dynamics [5]).


## 3.1. Preparation

Notation 4.
SetRD=sx∈ℕ∗,∃RDx,s=RDx,s∈I,O≥1.
That is,∀x∈ℕ∗, if RDx exists, then RDx=s will be included in SetRD, which is a set of existing reduced dynamics.
In this section, we will study two problems as follows:(1)
Inverse problem: given s∈SetRD, is it possible to derive starting integer x such that RDx=s?(2)
What is thesufficient and necessary conditions for any existing reduced dynamics, that is, given s∈I,O≥1, how to decide whether s∈SetRD?
Before exploring general situations, we give two trivial cases.Proposition 7.
O∈SetRD and IO∈SetRD.Proof (straightforward).
RDx∈02=O and RDx∈14=IO by Proposition 5.
In the following, we thus mainly concentrate onx∈34, where their reduced dynamics presents the form such as Ip≥2OI,Oq≥1,p,q∈ℕ∗ once it exists (recall Proposition 6).Theorem 3 (subset theorem).
Supposes∈SetRD, s≥2, x∈ℕ∗, i=0,1,…,s−2. We have(1.1)xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈02(1.2)xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈02(2.1)xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈12(2.2)xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈12Proof.
Wheni=0, there exists two and only two cases as follows:(1)
IfGetSs,i+1,1=O, then GetSs,1,ix∈02. There exists two subcases as follows:(1.1) IfGetSs,i+2,1=I, then OGetSs,1,ix∈12⟹GetSs,1,ix/2∈12⟹GetSs,1,ix∈24⊂02. Thus, xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈02.(1.2) IfGetSs,i+2,1=O, then OGetSs,1,ix∈02⟹GetSs,1,ix/2∈02⟹GetSs,1,ix∈04⊂02. Thus, xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈02.(2)
IfGetSs,i+1,1=I, then GetSs,1,ix∈12. There exist two subcases as follows:(2.1) IfGetSs,i+2,1=I, then IGetSs,1,ix∈12⟹3∗GetSs,1,ix+1/2∈12⟹3∗GetSs,1,ix+1∈24⟹3∗GetSs,1,ix∈14⟹GetSs,1,ix∈34⊂12. Thus, xGetSs,1,i+1x∈12⊂xGetSs,1,ix∈12.(2.2) IfGetSs,i+2,1=O, then IGetSs,1,ix∈02⟹3∗GetSs,1,ix+1/2∈02⟹3∗GetSs,1,ix+1∈04⟹3∗GetSs,1,ix∈34⟹GetSs,1,ix∈14⊂12. Thus, xGetSs,1,i+1x∈02⊂xGetSs,1,ix∈12.
We can prove similarly fori=1,2,…,s−2.Corollary 5.
Supposes∈SetRD, s≥2, i=0,1,…,s−2, x∈ℕ∗. We have(1.1)xGetSs,1,i+1x∈12=xGetSs,1,ix∈24(1.2)xGetSs,1,i+1x∈02=xGetSs,1,ix∈04(2.1)xGetSs,1,i+1x∈12=xGetSs,1,ix∈34;(2.2)xGetSs,1,i+1x∈02=xGetSs,1,ix∈14Proof.
Straightforward by Theorem3.Remark 10.
(1)
Corollary5 states that the residue classes are partitioned regularly into halves and either half will present either next intermediate transformation in terms of I or O (indeed, the partition property is thoroughly explored and proved in my other paper [8]. Note that this paper is independent from the cited paper.)(2)
Note that Theorem3 is not only guaranteed for reduced dynamics but also for original dynamics.Corollary 6.
Supposes∈SetRD, s≥2, i=2,3,…,s, x∈ℕ∗. We have(8)xIs MatchedGetSs,1,i−1x,GetSs,i,1=True⊂xIs MatchedGetSs,1,i−2x,GetSs,i−1,1=True.Proof.
Straightforward by Theorem3.
Roughly speaking, above corollary asserts that the last parity requirement is sufficient to guarantee all previous parity requirements. That is, the residue equation for last parity requirement is sufficient for deriving the required residue class for satisfying all parity requirements.
In the following, notationim is extended in which i could be larger than m or less than 0. That is, im=xx=k∗m+i,k∈ℕ,i∈ℤ,m∈ℕ∗,m≥2. ℤ is the integer.Lemma 1.
a∈ℕ,x,b,c∈ℕ∗,b≥2, thus(1)
x+c∈ab⟺x∈a−cb(2)
c∗x∈ab⟺x∈c−1∗ab, if gcdc,b=1(3)
x/c∈ab⟺x∈a∗cb∗cProof.
(1)x+c∈ab⟺x+c=k∗b+a,k∈ℕ⟺x=k∗b+a−c⟺x∈a−cb.
(2)(9)c∗x∈ab⟺c∗x=k∗b+a,k∈ℕ⟺k′∗b+cb∗x=k∗b+a,∵c=k′∗b+cb,k′∈ℕ⟺cb∗x=k−k′∗x∗b+a⟺cb∗x∈ab⟺c−1b∗cb∗x∈c−1b∗ab∵gcdc,b=1,∃c−1b,s.t.c−1b∗cb=1b⟺x∈c−1∗ab.
(3)x/c∈ab⟺x/c=k∗b+a,k∈ℕ⟺x=k∗b∗c+a∗c,k∈ℕ⟺x∈a∗cb∗c.
Indeed, ifgcdc,b=1, then c−1b exists and is the inverse of cb in group ℤ/bℤ∗=ℤ/bℤ∖0,∗modb such that c−1b∗cb=1b.


## 3.2. Derivex if RDx = IpOq

In this section, we assumep,q∈ℕ∗,p≥2, x∈34 if no explicitly declaration exists.Lemma 2.
Supposep,q∈ℕ∗,p≥2.
∃x∈34 such that RDx=IpOq, if and only ifReq-I):Ipx∈02qReq-II):IpOqx<x∧IpOq−1x<xProof.
By Theorem3 or Corollary 6, all parity sequence can be guaranteed if the last parity requirement is guaranteed.
IpOq−1x∈02⟺Ipx/2q−1∈02⟺Ipx∈02q, by Lemma 1 (3).
Thus, Req-I is sufficient for the requirements for all parities.
Anyx such that IpOq−1x<x can guarantee IpOix>x,i=1,2,…,q−2, because IpOix=IpOq−1x∗2q−1−i. Besides, Iix>x,i=1,2,…,p, due to Ix=3∗x+1/2>x. Thus, Req-II is sufficient for the requirements for all transformed integers.
Next, we check the requirement for Req-I.Lemma 3.
Ipx∈02q⟺x∈3p−1∗2p−12p+q.Proof.
Ipx∈02q
⟺3/2px+1−1∈02q∵ Equation (2)
⟺3/2px+1∈12q∵ Lemma 1(1)
⟺3px+1∈2p2p+q∵ Lemma 1(3)
⟺3p2p+qx+1∈2p2p+q∵ Lemma 1(2)
⟺x+1∈3p−1∗2p2p+q∵ Lemma 1(2) and gcd3p,2p+q=1⟺x∈3p−1∗2p−12p+q∵ Lemma 1 (1)
Indeed,3p−12p+q is the inverse of 3p2p+q in group ℤ/2p+qℤ∗=ℤ/2p+qℤ∖0,∗mod2p+q. Besides, even if p=1, the above lemma still holds due to Corollary 2 and Remark (3).
Next, we explore Req-II, assuming that Req-I is already guaranteed—x∈3p−1∗2p−12p+q.Notation 5.
λ=log21.5.Lemma 4.
IpOqx<x∧IpOq−1x≥x⟺q=λ∗p∧x>3p−2p/2p+q−3p.Proof.
(1)IpOqx<x⟺3/2px+1−1/2q<x∵ equation (2)(10)⟺3px+3p<2qx+12p⟺3px+3p<2p+qx+2p⟺3p−2p<2p+q−3px∵x>0,3p−2p>0⟺2p+q−3p>0∧x>3p−2p2p+q−3p.
(2)2p+q−3p>0⟺2q>3p/2p⟺q>log21.5∗p⟺q≥log21.5∗p, since q∈ℕ∗,log21.5∈ℚ,log21.5∗p∈ℕ∗.
(3)IpOqx<x∧IpOq−1x≥x⟺q=log21.5∗p, as q is the minimal one in q≥log21.5∗p.
Next theorem proves thatq=λ∗p is the necessary condition for IpOq∈SetRD.Theorem 4.
IfIpOq∈SetRD,p,q∈ℕ∗,p≥2, then(1)
∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq(2)
q=λ∗pProof.
It is straightforward due to Lemmas2–4.
Next theorem proves thatq=λ∗p is also the sufficient condition for IpOq∈SetRD.Theorem 5.
Ifq=λ∗p, p,q∈ℕ∗,p≥2, then(1)
∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq(2)
IpOq∈SetRDProof.
It is due to Lemmas2–4.
Next corollary claims sufficient and necessary condition forIpOq∈SetRDp≥2.Corollary 7.
q=λ∗p⟺IpOq∈SetRD, where p,q∈ℕ∗,p≥2.Proof.
It is straightforward by Theorems4 and 5.
Next corollary extends above corollary by tackling the casesp=0 and p=1.Corollary 8.
q=max1,λ∗p⟺IpOq∈SetRD, where p∈ℕ,q∈ℕ∗.Proof.
(1)p=0 and q=max1,0=1. I0O1=O∈SetRD, as RDx∈02=O.
(2)p=1 and q=max1,λ∗1=λ∗1=1. I1O1=IO∈SetRD, as RDx∈14=IO.
(3)p≥2 and q=max1,λ∗p=λ∗p. IpOq∈SetRD due to Corollary 7.
Inverse direction can be proved similarly.Corollary 9.
SetRD=+∞.Proof.
∀p∈ℕ∗,p≥2, let q=λ∗p. Thus, 2p+q>3p. ∃x∈3p−1∗2p−12p+q∧x>3p−2p/2p+q−3p such that RDx=IpOq. Hence, SetRD=+∞.


## 3.3. Derivex if RDx = Ip1Oq1Ip2Oq2…IpnOqn

In this section, we assumepi,qi∈ℕ∗, p1≥2, n≥2, and x∈34; if there exists no explicitly declaration.Lemma 5.
Supposes=Ip1Oq1Ip2Oq2…IpnOqn and kj=∑i=1jpi+qi, j=1,2,…,n−1.(1)
GetSs,1,kjx≥x⟹GetSs,1,kj−mx>x, m=1,2,…,qj(2)
GetSs,1,kjx≥x⟹GetSs,1,kj+mx>x, m=1,2,…,pj+1Proof.
Straightforward.(1)
BecauseGetSs,1,kjx≥x and GetSs,1,kj−mx=GetSs,1,kjx∗2m>GetSs,1,kjx, we have GetSs,1,kj−mx>x, m=1,2,…,qj(2)
BecauseGetSs,1,kjx≥x and GetSs,1,kj+mx=ImGetSs,1,kjx>GetSs,1,kjx (due to Ix>x), we have GetSs,1,kj+mx>x, m=1,2,…,pj+1Remark 11.
For better understanding the above lemma, we can explain the conclusion as follows: if “going Down” stage ends with a transformed integer that is not less than the starting integer, then all transformed integers in its “left” and “right” will be larger than the starting integer.Lemma 6.
Supposepi,qi∈ℕ∗,p1≥2,n≥2.
∃x∈34 such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, if and only ifReq-I):Ip1Oq1Ip2Oq2…Ipnx∈02qnReq-II):Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥xReq-III):Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1Proof.
Roughly speaking, Req-I is a residue equation to specify the requirement for parity sequence, and Req-II and Req-III are two inequalities to specify the requirements for transformed integers.(1)
Req-I is sufficient and necessary because of Theorem3.(2)
Req-II.Ip1Oq1Ip2Oq2…IpnOix=Ip1Oq1Ip2Oq2…IpnOqn−1x∗2qn−1−i. Thus,(11)Ip1Oq1Ip2Oq2…IpnOqn−1x≥x⟹Ip1Oq1Ip2Oq2…IpnOix>x,i=1,2,…,qn−2.Together withIp1Oq1Ip2Oq2…IpnOqnx<x, qn is thus the minimal one to let Ip1Oq1Ip2Oq2…IpnOix<x.(3)
Req-III. Obviously,Iix>x,i=1,2,…,p1. Besides, let s=RDx. By Lemma 5, we have(12)GetSs,1,∑i=1jpi+qix≥x,j=1,2,…,n−1⟹GetSs,1,kx>x,k=p1+1,p1+2,…,∑i=1n−1pi+qi+pn.Lemma 7.
Ip1Oq1Ip2Oq2…Ipnx∈02qn,n,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n,⟺x∈−∑i=1nAiBiCi−1Cn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, and Ci=2∑j=1ipj+qj,C0=1.The proof is somewhat straightforward but the computation is tedious; we thus move them to Appendix (Section4.1).Remark 12.
(1)
The conclusion forn=1 is identical with that in Theorem 5.(2)
Whenp1=q1=1, the conclusion 3−p12p1−12p1+q1=3−1∗2−14=3∗2−14=14, which is identical with that in Proposition 7. Thus, p1≥2 in Lemma 7 can be extended to p1≥1.
Next lemma is stated only forx∈−∑i=1nAiBiCi−1Cn, since Req-I should be guaranteed for ordered parity sequence firstly.Lemma 8.
Ip1Oq1Ip2Oq2…IpnOqnx<x,n,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n⟺x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0.Proof.
(13)Ip1Oq1Ip2Oq2…IpnOqnx<x⟺∏i=1naix+∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn<x,(due to the equation in the proof of Lemma 7 (7)) ⟺1−∏i=1naix>Ψ
whereΨ=∏i=2naib1+∏i=2naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn(14)⟺1−∏i=1n3pi2pi+qi∗x>Ψ⟺1−3∑i=1npi2∑i=1npi+qi∗x>Ψ⟺x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0,∵x>0,Ψ>0.
Indeed,(15)Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+anbn−1+bn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+3pn2pn+qn3pn−1−2pn−12pn−1+qn−1+3pn−2pn2pn+qn=3p1−2p13∑i=2npi2∑i=1npi+qi+3p2−2p23∑i=3npi2∑i=2npi+qi+⋯+3pn−1−2pn−13pn2pn+qn+pn−1+qn−1+3pn−2pn2pn+qn.Remark 13.
(1)
Whenn=1, Ψ=3pn−2pn/2pn+qn=3p1−2p1/2p1+q1:(16)Ip1Oq1x<x⟺x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi∧2∑inpi+qi−3∑inpi>0⟺x>Ψ∗2p1+q12p1+q1−3p1∧2p1+q1−3p1>0⟺x>3p1−2p12p1+q1∗2p1+q12p1+q1−3p1∧2p1+q1−3p1>0⟺x>3p1−2p12p1+q1−3p1∧2p1+q1−3p1>0,which is exactly identical with that of Theorem5. Therefore, the conclusion can be extended to n=1.(2)
Whenn=1 with p1=1,q1=1. x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi=3p1−2p1/2p1+q1−3p1=3−2/22−31=1/1=1. It is consistent with the conclusion in Proposition 7 for RDx∈14=IO.
Note that, here,2∑inpi+qi−3∑inpi>0 is a necessary condition for Ip1Oq1Ip2Oq2…IpnOqnx<x.
Next, we check the requirement Req-III. Again, the next lemma is discussed only forx∈−∑i=1nAiBiCi−1Cn, since Req-I should be guaranteed for designated parity sequence as a prerequisite.Lemma 9.
Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1,n≥2⟺2∑ijpi+qi−3∑ijpi<0.Proof.
Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1(17)⟺∏i=1jaix+∏i=2jaib1+∏i=3jaib2+⋯+∏i=j−1jaibj−2+∏i=jjaibj−1+bj≥x,(due to the equation in the proof of Lemma 7 (7)) ⟺1−∏i=1jaix≤Ψj
where(18)Ψj=∏i=2jaib1+∏i=3jaib2+⋯+∏i=j−1jaibj−2+∏i=jnaibj−1+bj⟺1−∏i=1j3pi2pi+qi∗x≤Ψj⟺1−3∑i=1jpi2∑i=1jpi+qi∗x≤Ψj⟺x≤Ψj∗2∑i=1jpi+qi2∑i=1jpi+qi−3∑i=1jpi∧2∑ijpi+qi−3∑ijpi>0∨2∑ijpi+qi−3∑ijpi<0.
Next, we will prove that2∑ijpi+qi−3∑ijpi>0,j=1,2,…,n−1 is impossible by contradiction.
SupposeIp1Oq1Ip2Oq2…Ipjx∈02qj⟺x∈Sj,j=1,2,…,n. By Lemma 6 (1) or Theorem 3, Sj+1⊂Sj,j=n−1,n−2,…,1.
Suppose∃j∈1,n−1 such that 2∑ijpi+qi−3∑ijpi>0. Select the minimal one in them (thus, for 1≤k≤j−1, 2∑ikpi+qi−3∑ikpi<0). Because of the generality of n in qn in Lemma 8, we have Ip1Oq1Ip2Oq2…IpjOqjx<x, when x>Ψj′=Ψj∗2∑i=1jpi+qi/2∑i=1jpi+qi−3∑i=1jpi, j∈1,n−1.
LetΨn′=Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.
Therefore, ifx>maxΨj′,Ψn′ and x∈Sn, then Ip1Oq1Ip2Oq2…Ipjx∈02qj, Ip1Oq1Ip2Oq2…IpjOqjx<x, and Ip1Oq1Ip2Oq2…IpkOqkx≥x,k=1,2,…,j−1. Thus, RDx∈Sn=Ip1Oq1Ip2Oq2…IpjOqj, which contradicts with RDx∈Sn=Ip1Oq1Ip2Oq2…IpnOqn in assumption. Thus, ∄j∈1,n−1,2∑ijpi+qi−3∑ijpi>0. That is, 2∑ijpi+qi−3∑ijpi<0,j=1,2,…,n−1.Lemma 10.
2∑inpi+qi−3∑inpi>0⟺∑i=1nqi≥λ∗∑i=1npi.Proof.
LetU=∑inpi,D=∑inpi+qi:(19)2∑inpi+qi−3∑inpi>0⟺2D>3U⟺D>log23∗U⟺D≥log23∗U,∵U,D∈ℕ∗,log23∈ℚ∗,log23∗U∈ℕ∗⟺D−U≥log23∗U−U⟺D−U≥log23∗U−U⟺D−U≥log21.5∗U⟺∑i=1nqi≥λ∗∑i=1npi.Lemma 11.
2∑ijpi+qi−3∑inpi<0⟺∑i=1jqi≥λ∗∑i=1jpi,j=1,2,…,n−1.Proof.
LetU′=∑ijpi,D′=∑ijpi+qi:(20)2∑ijpi+qi−3∑ijpi<0⟺2D′<3U′⟺D′<log23∗U′⟺D′≤log23∗U′−1,∵U′,D′∈ℕ∗,log23∈ℚ∗,log23∗U′∈ℕ∗⟺D′−U′≤log23∗U′−U′−1⟺D′−U′≤log23∗U′−U′−1⟺D′−U′≤log21.5∗U′−1⟺∑i=1jqi<λ∗∑i=1jpi.Lemma 12.
Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x⟺qn=λ∗∑i=1npi−∑i=1n−1qi∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.Proof.
By Lemma10, ∑i=1nqi≥λ∗∑i=1npi.
Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x, thus qn is the minimal one. Therefore, qn=λ∗∑i=1npi−∑i=1n−1qi.Theorem 6.
IfIp1Oq1Ip2Oq2…IpnOqn∈SetRD, pi,qi∈ℕ∗,p1≥2, i=1,2,…,n, n∈ℕ∗,n≥2, then(1)
∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1, Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,bi=3pi−2pi/2pi+qi,i=1,2,…n(2)
∑i=1nqi=λ∗∑i=1npi∧∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1,n≥2Proof.
It is straightforward due to Lemmas7–12.
Next theorem proves that∑i=1nqi=λ∗∑i=1npi and ∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1,n≥2 is also the sufficient condition for Ip1Oq1Ip2Oq2…IpnOqn∈SetRD.Theorem 7.
If∑i=1nqi=λ∗∑i=1npi, ∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1, pi,qi∈ℕ∗,p1≥2. i=1,2,…,n, n∈ℕ∗,n≥2, then(1)
∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=Ip1Oq1Ip2Oq2…IpnOqn, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, and Ci=2∑j=1ipj+qj,C0=1; Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qiandbi=3pi−2pi/2pi+qi,i=1,2,…,n(2)
Ip1Oq1Ip2Oq2…IpnOqn∈SetRDProof.
By Lemma12,(21)∑i=1nqi=λ∗∑i=1npi∧x>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi⟹Ip1Oq1Ip2Oq2…IpnOqnx<x∧Ip1Oq1Ip2Oq2…IpnOqn−1x≥x.
Together withx∈−∑i=1nAiBiCi−1Cn, we have Ip1Oq1Ip2Oq2…Ipnx∈02qn due to Lemma 7.
Besides,Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1 by Lemmas 9 and 11. Therefore, by Lemma 6, ∃x∈ℕ∗,RDx=Ip1Oq1Ip2Oq2…IpnOqn.
Note that the above theorem indeed implies thatRDx=RDx+P=Ip1Oq1Ip2Oq2…IpnOqn, where P=2p1+q1+p2+q2+⋯+pn+qn=2∑i=1npi+qi=2RDx when x is sufficient large (i.e., x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi).
Indeed, the requirement for being sufficient large can be omitted and proved by us in another paper [9]. Note that this paper is independent with cited paper.
Following corollary states the necessary and sufficient condition for guaranteeing that anyIp1Oq1Ip2Oq2…IpnOqn, where pi,qi∈ℕ∗,p1≥2 and i=1,2,…,n,n∈ℕ∗,n≥2, is a reduced dynamics of some x∈ℕ∗.Corollary 10.
∑i=1nqi=λ∗∑i=1npi,pi,qi∈ℕ∗,p1≥2,i=1,2,…,n,n∈ℕ∗,n≥2∧∑i=1jqi<λ∗∑i=1jpi,j=1,2,…,n−1⟺Ip1Oq1Ip2Oq2…IpnOqn∈SetRD.Proof.
Straightforward due to Theorems6 and 7.Theorem 8 (prefix-free theorem).
Supposepi,qi∈ℕ∗,i=1,2,…,n, p1≥2,n≥2. If s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, then GetSs,1,∑i=1jpi+qi∈SetRD,j=1,2,…,n−1.Proof.
Ip1Oq1Ip2Oq2…IpnOqn∈SetRD
⟹∀x∈−∑i=1nAiBiCi−1Cn,Ip1Oq1Ip2Oq2…IpjOqjx≥x,j=1,2,…,n−1
⟹2∑ijpi+qi−3∑ijpi<0,j=1,2,…,n−1∵ Lemma 9
⟹∄x∈ℕ∗,GetSs,1,∑i=1jpi+qix<x∵ Lemma 8
⟹GetSs,1,∑i=1jpi+qi∈SetRD,j=1,2,…,n−1.
Simply speaking, Theorem8 shows that SetRD is prefix-free. Regarding more general conclusion by including O or IO (i.e., for x∈34) and n=1 (i.e., for IpOq), we have following corollary.Corollary 11.
s∈SetRD⟹sI,O≥1⊂SetRD.Proof.
Straightforward.
Next, we give more general results by introducing two functions as follows:Definition 6.
FunctionCntI⋅. CntI:c⟶y takes as input c∈I,O≥1, and outputs y∈ℕ that is the count of “I” in c.Definition 7.
FunctionCntO⋅. CntO:c⟶y takes as input c∈I,O≥1, and outputs y∈ℕ∗ that is the count of “O” in c.
For example,CntIIIOO=2, CntOIIOO=2, CntIIIOIO=3, and CntOIIOIO=2.
Corollary 8 states thesufficient and necessary condition for s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, n≥2. It can be extended by using GetSs,1,k,k=1,2,…,s−1 instead of GetSs,1,∑i=1jpi+qi as follows.Corollary 12.
s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, pi,qi∈ℕ∗, p1≥2, i=1,2,…,n, n∈ℕ∗, n≥2, if and only if(1)
CntOs=λ∗CntIs(2)
CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1Proof.
Straightforward.
Ifn=1 and p=0,1 for IpOq are both included, the above corollary can be extended to the following corollary.Corollary 13.
s=Ip1Oq1Ip2Oq2…IpnOqn∈SetRD, pi∈ℕ, qi∈ℕ∗, i=1,2,…,n,n∈ℕ∗, if and only if(1)
p1=0,n=1. s=O(2)
p1≥1. CntOs=λ∗CntIs, and CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1Proof.
(1)
It is trivials=O⟹s∈SetRD. Inversely, n=1,p1=0,s=Ip1Oq1=Oq1∈SetRD⟹s=O.(2)
n=1, s=Ip1Oq1,p1,q1∈ℕ∗.(2.1)p1=1. GetSs,1,1=I. Obviously, CntOGetSs,1,1=0<λ∗CntIGetSs,1,1=λ∗1=log21.5=1.s=IOq1, thus GetSs,1,2=IO. Then, CntOGetSs,1,2=1, λ∗CntIGetSs,1,2=λ∗1=1. Thus, s=2 and s=IO. Obviously, IO∈SetRD.Inversely,s=IO∈SetRD⟹CntOs=1=λ∗1=λ∗CntIs∧ (CntOGetSs,1,k=0<λ∗CntIGetSs,1,k=1,k=s−1=1).(2.2)p1≥2. q1=λ∗p1⟺Ip1Oq1∈SetRD by Corollary 7. Thus, q1=λ∗p1⟺CntOs=λ∗CntIs because CntOs=q1,CntIs=p1.Besides,q1=λ∗p1⟹CntOGetSs,1,k<λ∗CntIGetSs,1,k, k=1,2,…,s−1. The reason is as follows:Whenk=1,2,…,p1, CntOGetSs,1,k=0<λ∗CntIGetSs,1,k∈ℕ∗ is trivial.Whenk=p1+1,p1+2,…,p1+q1−1,q1=λ∗p1⟹CntOGetSs,1,k=k−p1≤q1−1<q1=λ∗p1=λ∗CntIGetSc,1,k as p1=CntIGetSs,1,k.(3)
n≥2. p1≥2. By Corollary 10, CntOc=λ∗CntIc∧CntOGetSs,1,k<λ∗CntIGetSs,1,k,k=1,2,…,s−1⟺s∈SetRD.
Next, we useCntO⋅ and CntI⋅ to restate sufficient and necessary condition for s∈SetRD as follows.Corollary 14 (form corollary).
s∈I,O≥1 is a reduced dynamics, if and only if(1)
s=1,s=O.(2)
s≥2,(22)CntOs=λ∗CntIs,CntOs′<λ∗CntIs′,s′=GetSs,1,i,i=1,2,…,s−1.Proof.
It is straightforward due toTheorem8 and Corollary 8–11.
Finally, we obtain the following inverse theorem as a summary.Theorem 9 (inverse theorem).
(1)
Ifs=1,s=O, then ∃x∈02 such that RDx=O(2)
Ifs≥2, s=Ip1Oq1Ip2Oq2…IpnOqn, pi,qi∈ℕ∗, i=1,2,…,n,n∈ℕ∗, CntOs=λ∗CntIs,CntOs′<λ∗CntIs′, s′=GetSs,1,k,k=1,2,…,s−1
Then,∃x∈−∑i=1nAiBiCi−1Cn∧x>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi such that RDx=s, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1, Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,bi=3pi−2pi/2pi+qi.Proof.
It is straightforward due to Theorem7 and form corollary (Corollary 12).
Following corollary states thatSetRD can be constructed by generating s∈I,O≥1 which satisfies requirements algorithmically instead of by conducting concrete Collatz transformations for enumerated starting integers.Corollary 15.
SetRD=O∪ss∈I,OL,L∈ℕ∗,L≥2,CntOs=λ∗CntIs,CntOs′<λ∗CntIs′,s′=GetSs,1,i,i=1,2,…,L−1.Proof.
It is straightforward due to Corollary12.
Following corollary states the relations betweenCntIs and CntOs+CntIs=s, s∈SetRD. Indeed, CntIs is the count of 3∗x+1/2 that equals the count of 3∗x+1 computation, and CntOs+CntIs equals the total count of x/2 computation in reduced dynamics.Corollary 16.
Ifs∈SetRD, then(1)
D≥log23∗U, where U=CntIs, D=s(2)
3U<2DProof.
(1) Whens=O, U=0, D=1. 1>log23∗0=0 by Corollary 13.
Whens≠O, s∈SetRD⟹D=CntOs+CntIs=log21.5∗CntIs+CntIs=log21.5∗U+U=log23∗U by Corollary 13.
In summary,s∈SetRD⟹D≥log23∗U, and note that “>” is obtained when and only whens=O.
(2)D≥log23∗U⟹D≥log23U⟹3U≤2D⟹3U<2D.Corollary 17.
s∈SetRD,s≥2⟹3CntIGetSs,1,i>2i, i=1,2,…,s−1.Proof.
Lets′=GetSs,1,i,i=1,2,…,s−1. Obviously, s′=i.
s∈SetRD⟹CntOs′<log21.5∗CntIs′∵ Corollary 12(23)⟹CntOs′<log21.5∗CntIs′,∵log21.5∈ℚ,CntIs,CntOs∈ℕ∗⟹CntOs′+CntIs′<log23∗CntIs′⟹s′<log23∗CntIs′⟹2s′<3CntIs′⟹3CntIGetSs,1,i>2i.Example 3.
By using the conclusion in fForm corollary (Corollary12), CntOs can be computed from CntIsdirectly as follows:(1)
s∈I,O≥1,s∈SetRD, CntIs=1⟹CntOs=λ∗CntIs=λ∗1=log21.5∗1=0.58496250∗1=1(2)
s∈I,O≥1,s∈SetRD, CntIs=2⟹CntOs=λ∗CntIs=λ∗2=log21.5∗2=0.58496250∗2=2(3)
s∈I,O≥1,s∈SetRD, CntIs=3⟹CntOs=λ∗CntIs=λ∗3=log21.5∗3=0.58496250∗3=2(4)
s∈I,O≥1,s∈SetRD, CntIs=4⟹CntOs=λ∗CntIs=λ∗4=log21.5∗4=0.58496250∗4=3
Due to inverse theorem (Theorem9), each s∈SetRD cannot map to more than one residue class with the module 2s. Thus, a function called Invrs can be defined as follows.Definition 8.
FunctionInvrs⋅. Invrs:s⟶rs takes input
s=O or(24)s=Ip1Oq1Ip2Oq2…IpnOqn∈I,O≥2,pi,qi∈ℕ∗,i=1,2,…,n,n∈ℕ∗CntOs=log21.5∗CntIs,CntOs′<log21.5∗CntIs′,s′=GetSs,1,k,k=1,2,…,s−1,and outputs r=02 when s=O, or(25)r=−∑i=1nAiBiCi−12c∩xx>Ψ∗2∑i=1npi+qi2∑i=1npi+qi−3∑i=1npi,when s≥2, where Ai=3pi−2pi, Bi=3∑j=1ipj−1modCn, Ci=2∑j=1ipj+qj,C0=1Ψ=∏i=2naib1+∏i=3naib2+⋯+∏i=n−1naibn−2+∏i=nnaibn−1+bn, ai=3pi/2pi+qi,andbi=3pi−2pi/2pi+qi.
The following corollary states thatInvrs⋅ is injective. It is straightforward because the reduced dynamics of a starting integer is unique (Proposition 3).Corollary 18.
∀s1,s2∈SetRD,s1≠s2⟹r1≠r2, where r1=Invrss1 and r2=Invrss2.Proof.
It is straightforward by proving converse-negative proposition:(26)r1=r2⟹RDx∈r1=RDx∈r2⟹s1=s2.
IfInvrs⋅ is surjective, then Collatz conjecture will be true. That is, if ∪s∈SetRDInvrss=ℕ∗, then Collatz conjecture will be true. However, it is difficult to be proved because each residue class is partial due to the requirement of xx>Ψ∗2∑i=1npi+qi/2∑i=1npi+qi−3∑i=1npi.
(Thanks to the period theorem that is proved in [9]; this requirement can be omitted. Besides, all the above conclusions, e.g., subset theorem (Theorem 3), prefix-free theorem (Theorem 8), form corollary (Corollary 12), and Inverse theorem (Theorem 9), can be observed in my proposed tree-based graph to present reduced dynamics [5]).


## 4. Conclusion

We useRDx to denote the reduced dynamics of x, which is represented by a sequence of computation of “I” or “O,” where “I” denotes 3∗x+1/2 and “O” denotes x/2.This paper discovered and proved two major facts as follows:(1)
The relation between the count ofx/2 (i.e., “O”) and the count of 3∗x+1/2 (i.e., “I”) in any reduced dynamics is proved by form corollary (Corollary 12). That is, given any s∈I,O≥1, the sufficient and necessary condition for s∈SetRD is as follows:(i)
s=1,s=O(ii)
s≥2, CntOs=λ∗CntIs,λ=log21.5,CntOs′<λ∗CntIs′,s′=GetSs,1,i,i=1,2,…,s−1Therefore, any reduced dynamics can be generated by guaranteeing sufficient and necessary condition in form Corollary, instead of by enumerating all integers one by one and computing concrete Collatz transformations step by step. That is,SetRD=O ∪ {ss∈I,OL,L∈ℕ∗, L≥2, CntOs=λ∗CntIs, CntOs′<λ∗CntIs′, s′=GetSs,1,i, i=1,2,…,L−1}.IfCntOs=λ∗CntIs, then reduced dynamics will be available. That is, if and only if the count of “O” is larger than λ=log21.5 times the count of “I,” then reduced dynamics will be available (i.e., transformed integer will be less than starting integer immediately).The count ofx/2 equals CntOs+CntIs and the count of 3∗x+1 equals CntIs. CntOs+CntIs=λ∗CntIs+CntIs=λ∗CntIs+CntIs=λ+1∗CntIs. In other words, if and only if the count of x/2 computation over the count of 3∗x+1 computation is larger than λ+1=log21.5+1=log23=ln3/ln2, then the transformed integer will be less than the starting integer.(2)
Given a reduced dynamics, a residue class of the starting integer can be derived by inverse theorem (Theorem9). That is, given s∈SetRD, a residue class r can be calculated from s directly by proposed formula (algorithm), such that RDx∈r=s, where the module of r is 2s (for sufficient large x).



---

*Source: 5946759-2020-08-25.xml*