I. INTRODUCTION

The $3x+1$ problem, also known as the Collatz conjecture, $3x+1$ mapping, Ulam conjecture, Kakutani's problem, Thwaites conjecture, Hasse's algorithm, or Syracuse problem [1], is one of the unsolved problems in mathematics. Paul Erdos (1913-1996) commented on the intractability of the $3x+1$ problem [2], stating that "Mathematics is not ready for those problems yet".

The $2x+1$ problem states that, for any positive integer $x$, if $x$ is even, divide it by 2; if $x$ is odd, multiply it by 3 and add 1. Repeating this process continuously leads to the conjecture that no matter which number is initially chosen, the result will always reach 1 eventually.

We use the notations as in [4,7], and describe a Collatz function as follows:

Let $N$ denote the set of positive integers. For $n\in N$, and $k=0,1,2,3,\dots ,T^0(n)$ and $T^{k+1}(n)$ denote $n$ and $T(T^k(n))$, respectively. Concerning the behavior of the iteration of the Collatz function, for any integer $n$, there must exist an integer $r$ so that

a) The

We convert the last row of numbers into the first column to get a modified Sarkovskii ordered integer lattice[6] as the following,

• 1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
• 2, 2·3, 2·5, 2·7, 2·9, 2·11, 2·13, 2·15, 2·17, 2·19,...
• $2^2,2^2\cdot 3,2^2\cdot 5,2^2\cdot 7,2^2\cdot 9,2^2\cdot 11,2^2\cdot 13,2^2\cdot 15,2^2\cdot 17,2^2\cdot 19,\dots$
• $2^3,2^3\cdot 3,2^3\cdot 5,2^3\cdot 7,2^3\cdot 9,2^3\cdot 11,2^3\cdot 13,2^3\cdot 15,2^3\cdot 17,2^3\cdot 19,\dots$
• $2^4,2^4\cdot 3,2^4\cdot 5,2^4\cdot 7,2^4\cdot 9,2^4\cdot 11,2^4\cdot 13,2^4\cdot 15,2^4\cdot 17,2^4\cdot 19,\dots$

...

In the first row, they are odd numbers from left to right, that are 1, 3, 5, 7, 9, 11, 13, $\cdots$. From the second row, each number is two times the number in its previous row, and so on.

b) The

If we draw a line segment with an arrow between two digits in the lattice of integers in the modified Sarkovskii ordering, one being the original value $x$ and the other being its value of the Collatz function $T(x)$, and then connect $T(x)$ to $T^2(x)$, and so on $T^2(x)$ to $T^3(x),\dots$, we get a graph which can be called a Collatz graph.

Fig. 1: The Collatz graph of $T^{16}(7)=T(5,11,7)=1$ in the lattice of integers in the modified Sarkovskii ordering and the algebraic formula.

For different integers $k$ and $l$, if there is a common vertex in their Collatz graphs, their graphs will overlap from that point onwards until they reach the minimum value of 1. Using the Collatz function $T(x)$, we can obtain an algebraic formula of $\frac{1}{2^4},\frac{3}{2^7},\frac{3^2}{2^9},\dots ,\frac{3^m}{2^r}\cdot x$, where $r$ is the number of vertical segments and $m$ is the number of oblique segments in the Collatz graph,

For example, $n=7$, $7\to 22\to 11\to 34\to 17\to 52\to 26\to 13\to 40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1\to \dots$, the algebraic formula is

and the Collatz graph is Fig.

And $n=36$, $36\to 18\to 9\to 28\to 14\to 7\to 22\to 11\to 34\to 17\to 52\to 26\to 13\to 40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1\to \dots$, the algebraic formula is

and the Collatz graph is Fig. 2.

Fig. 2: The Collatz graph of $T^{21}(36)=T(6,15,36)=1$ in the lattice of integers in the modified Sarkovskii ordering and the algebraic formula.

We observe that there is a property present,

Proposition 1 For positive integers $i,j,k,l$, and $l_k,l_{k-1},\dots ,l_1$, if , then there is a recurrence relation

where $k+l=i-j$, and $l\ge l_k\ge l_{k-1}\ge \cdots \ge l_1$.

For example, there are

We can get the recurrence formula about the Collatz function,

II. NUMERICAL EXAMPLE

Using the above Collatz graphs of the integer lattice of the modified Sarkovskii ordering, we give the following algebraic formulas,

Example 2 For the formula

we rewrite it as an integer equation,

Proof. To calculate the power of 3 and the value of 18 using powers of 2,

substituting these expressions into the left-hand side of the above equation, one obtains,

and get the value $2^{14}$ which is equal to the right value of the equation.

III. CONVERT THE INTEGER NUMBER FROM DECIMAL TO BINARY

Be inspired by the above, we use binary to rewrite the Collatz function (1) as the following formulas (2) and (3). We denote a binary number, which is a string of 0s and 1s, as $n=(1\times \cdots \times {)}_2$, where $\times$ is either 1 or 0, e.g. $3=(11{)}_2$,

The result is

Namely, when $n$ is an odd number, we multiply it with $(11{)}_2$ and add 1 to the end of the binary number. For example, $T(97)=T(1100001)$ in Fig. 3. When $n$ is an even number, the division is equal to deleting the zero at the end in the binary number. We give the iteration of the Collatz function for 1, 5, 7, 9, 97 in binary as the following five tables.

We convert the modified Sarkovskii ordered integer lattice[6] from decimal to binary as the follows,

Fig. 3: For the Collatz function $T(97)$ in binary, the first step is the multiplication in left, the second step is division in the right bottom.

Example 3 For positive integer 1, we manipulate the iteration of the Collatz function in both decimal and binary numbers,

1,	11,	101,	111,	1001,	1011,	1101,	1111,	10001,	···
10,	110,	1010,	110,	10010,	10110,	11010,	11110,	100010,	···
100,	1100,	10100,	1100,	100100,	101100,	110100,	111100,	1000100,	···
1000,	11000,	101000,	11000,	1001000,	1011000,	1101000,	1111000,	10001000,	···
10000,	110000,	1010000,	110000,	10010000,	10110000,	11010000,	11110000,	100010000,	···
···	···	···	···	···	···	···	···	···	···

ith	0	1	2	3
decimal	1	4	2	1
binary	1	100	10	1

Example 4 For positive integer $5=(101{)}_2$, we manipulate the iteration of the Collatz function in both decimal and binary numbers,

ith	0	1	2	3	4	5
decimal	5	16	8	4	2	1
binary	101	10000	1000	100	10	1

Example 5 For $7=(111{)}_2$, we manipulate the iteration of the Collatz function in both decimal and binary numbers.

ith	0	1	2	3	4	5	7	8	11	12	16
decimal	7	22	11	34	17	52	13	40	5	16	1
binary	111	10110	1011	100010	10001	110100	1101	101000	101	10000	1

Example 6 For $9=(1001{)}_2$, we manipulate the iteration of the Collatz function in both decimal and binary numbers.

ith	0	1	2	3	4	5	6	7	14	15	19
decimal	9	28	14	7	22	11	34	17	5	16	1
binary	1001	11100	1110	111	10110	1011	100010	10001	101	10000	1

Example 7 For $97=(1100001{)}_2$, we manipulate the iteration of the Collatz function in binary as the following table,

97	1100001	206	11001110	425	110101001	866	1101100010
292	100100100	103	1100111	1276	1001111100	433	110110001
146	10010010	310	100110110	638	100111110	1300	10100010100
73	1001001	155	10011011	319	100111111	650	1010001010
220	11011100	466	111010010	958	111011110	325	101000101
110	1101110	233	11101001	479	11101111	976	1111010000
55	110111	700	1010111100	1438	1011001110	488	111101000
166	10100110	350	101011110	719	101100111	244	11110100
83	1010011	175	10101111	2158	100001101110	122	1111010
250	11111010	526	1000001110	1079	10000110111	61	111101
125	1111101	263	100000111	3238	110010100110	184	10111000
376	10111000	790	1100010110	1619	11001010011	92	1011100
188	1011100	395	110001011	4858	100101111010	46	101110
94	101110	1186	10010100010	2429	100101111101	23	10111
47	101111	593	1001010001	7288	1110001111000	70	1000110
142	10001110	1780	11011110100	3644	111000111100	35	100011
71	1000111	890	1101111010	1822	11100011110	106	1101010
214	11010110	445	110111101	911	1110001111	53	110101
107	1101011	1336	10100111000	2734	101010101110	160	10100000
322	101000010	668	1010011100	1367	10101010111	80	1010000
161	10100001	334	101001110	4102	1000000000110	40	101000
484	111100100	167	10100111	2051	100000000011	20	10100
242	11110010	502	111110110	6154	1100000001010	10	1010
121	1111001	251	11111011	3077	110000000101	5	101
364	101101100	754	1011110010	9232	10010000010000	16	10000
182	10110110	377	101111001	4616	1001000001000	8	1000
91	1011011	1132	10001101100	2308	100100000100	4	100
274	100010010	566	1000110110	1154	10010000010	2	10
137	10001001	283	100011011	577	1001000001	1	1
412	110011100	850	1101010010	1732	11011000100

Corollary 8 The Collatz function makes an odd integer number in binary bigger by adding 1 or 2 bits to the left of the sequence of $1s$ and $0s$, and an even integer number in binary smaller by deleting all zeros at the end of the sequence of $1s$ and $0s$. Thus, although in some cases the value of The Collatz function $T(x)$ may be bigger than $x$ in decimal, in general, the iteration of the Collatz function will make an integer number smaller and smaller, eventually reaching the smallest positive integer number 1.

We can rewrite the Collatz conjecture in binary, which makes it an easier problem to solve, thus allowing us to completely solve the Collatz conjecture.

Fact 9 For any positive integer, under the Collatz function, the sequence of integer numbers in binary will eventually reach 1.

Proof. For an odd binary integer, we multiply it by $(11{)}_2$ and add 1 in the last bit, the result number must be an even number in binary which at least one zero at the end. We delete all these zeros, namely it is the division. This is the above corollary 8. Thus, we repeat this process as long as we can, because the bits of the sequence in binary of a positive integer number is finite. Eventually, we must in finitely steps reach the smallest positive integer number 1.

Remark 10 We can say that the $3x+1$ problem is a converse proposition of "period three implies chaos" [4], and it is also an example of any one positive integer number having a period of 3 in the Collatz function.

IV. CONCLUSIONS

We rewrite the Collatz function in binary, which makes the $3x+1$ problem easier. The multiplications of $(11{)}_2$ and divisions of $(10{)}_2$ make the positive integer number smaller and smaller with the iterations of the Collatz function. In some cases, the value of the Collatz function $T(x)$ may be bigger than $x$, thus allowing us to completely solve the Collatz conjecture.