A proof supporting the Collatz conjecture
Abstract
This paper presents a proof supporting the Collatz conjecture. To support the Collatz conjecture, a new general expression that can be interpreted in elementary number theory has been defined. This general expression represents the number of odd operations as m and the number of even operations as $n_i$, wheren_i is determined by m, and it is presented as an indeterminate equation of variable polynomials. By executing m Collatz operations on the defined general expression, it can be proven by mathematical induction that the resulting natural number is not equal to any given natural number. Therefore, there are no periodic sequences in Collatz operations. Furthermore, all given even numbers eventually encounter a form of $2^n$ through Collatz operations, and they converge to 1 with the next even Collatz operation.
key ward Collatz conjecture, Proof by Contradiction, Fermat's little theorem
１ Introduction About The Collatz Conjecture
Traditionally referred to by the name
$Rotor Collatz^{1,2}$ who introduced the idea in 1937. The Collatz A proof supporting the Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer 1. This arithmetic operation continues to divide by 2 until it becomes an odd number if it is even, and when it becomes odd, it multiplies by three and adds one. Barina, $David^3$ was Calculated that the conjecture has been shown to hold for all positive integers up to $2.95×10^{20}$.$Terence Tao^4$tell almost all orbits of the Collatz map attain almost bounded values. $ Yanliang,Xian^5$ is the only one who calculates the number of divisions as a variable. But he takes it as one variable. Baoyuan $Duan^6$ build two weight function models for the Collatz sequence, both of them can converge. The proof procedure is not perfect and strict because of various results after $( ×3 + 1 )2^k$ operation. If $A = 6$, then division occurs once. However, if the even number is 12, it will be divided by 2 twice. If the even number is 24, it will be divided by three times. If there is a cyclic sequence of values like 4→1→4→1 at values above 6, it will no longer converge to 1. According to $Christian Hercher^7$, it is said that there are no cycles in the Collatz operation for numbers less than $91$. $Christosr,Apadimttrio^8$ is said On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. In this paper, we define the number of Collatz operations from even to even as m, and consider the number of divisions during this period as a variable related to m, denoted as $2^{n_m} $, to construct a general formula for variable polynomial indeterminate equations. This definition successfully converges the discussion of existence and other inefficient proofs into a simple computation that anyone can understand. I don't think this general formula converges. This is because all positive numbers are expressed in the form of their sum. Therefore, I wondered if we would encounter $2^n$ during the calculations.This is because all positive numbers are expressed in the form of their sum. Therefore, I wondered if we would encounter $2^n$ during the calculations. This is because if you encounter $2^n$, it will converge to 1 in the next even Collatz operation.
2 Definition of a general formula
The Collatz operation is defined as follows.
\left\{ \begin{array}{ll}
a^o_m=a^e_m/{2^{n_m}} & n_m≔max{,n_m}: {2^{n_m}} ∈N:\text{even}) \\
a^e_{m+1}=3a_m^o+1 & a_m^o:\text{odd}:{a_m^o>1}
\end{array} \right.
When defined this way, it can be divided into odd $a_m^o$ and even $a^e_{m+1}$. However, the first operation for the even numbers will be n_1, followed by $ n_1, n_2$⋯⋯ and so on. Based on this definition, the number of odd operations m and the number of even operations n_m are used as variables to define the general formula. Let the first odd natural number be $a^o_1$ and the first even natural number be $a^e_1$. The result after repeating the specified odd operation m imes in the Collatz process will be $a^e_1$ and $a_m^e$.
If the given natural number is even,
a_1^o= \frac{a_1^e}{2^{n_1 }}
Here,$ n_1 $ is a variable with n_1≥1, and it is processed as an even number with 2 until it becomes odd. Then, an odd operation is performed,
a_2^e=3a_1^o+1
As a result,
a_2^e=3(a_1^e ⁄2^{n_1}) +1
Thereafter, the Collatz operation is repeated, and the general term is,
a^e_m= (3^{m-1} a_1^e+3^{m-2} k_1+3^{m-3} k_2+⋯+3k_{m-2}+k_{m-1} )⁄k_{m-1} : (1)
However, do the following,
k_m=2^{∑_{i=1}^mn_i}
3 The existence of a cyclic sequence
3－１Cyclic sequence from a single operation
The relationship between $a^e_2$ and $a_1^e$ is as follow.
a_2^e=3a_1^e/k_1 +1
If $ a_2^e=a_1^e$ is next.
$k_1 a_1^e=3a_1^e+k_1$
If $ a_2^e=a_1^e$ is next.
$k_1 a_1^e=3a_1^e+k_1$ $(k_1-3) a_1^e=k_1$ $a_1^e=k_1/(k_1-3) $
If $k_1< 3$, then the right side becomes a negative number, so the assumption that $a_2^e=a_1^e$ leads to a contradiction and $a_2^e≠a_1^e$. If it cannot be divided, the assumption that $a_2^e=a_1^e$ leads to a contradiction and $a_2^e≠a_1^e$. $k_1$ can be divided by 4, but since $a_1^e=4$, it converges to 1 in the first Collatz operation, so $a_1^e$ is not calculated. If $k_1≥8$ can be divided, then setting $a_1^e=2n$,
$a_1^e=k_1/((k_1-3) )=2n$ $k_1=2n(k_1-3)$
$(2n-1) k_1=2n3$ $k_1=2n3/(2n-1)≥8$
$2n3≥16n-8$ $8≥10n$
$=0.8≥n$
Since $n∉N$, it cannot be divided evenly, thus the assumption that $a_2^e=a_1^e$ leads to a contradiction, and $a_2^e≠a_1^e$.
3－２ Cyclic sequence from two operations
The relationship between $a_3^e$ and $a_1^e$ is,
$a_3^e=3^2/k_2 a_1^e+(3k_1)/k_2 +1$
If $a_3^e=a_1^e$ is next.
$a_1^e=3^2/k_2+(3k_1)/k_2 +1$ $k_2 a_1^e=3^2a_1^e+3k_1+k_2$
$(k_2-3^2 ) a_1^e=3k_1+k_2$ $a_1^e=(3k_1+k_2)/((k_2-3^2 ) )$
If $k_2<3^2$, the right side becomes a negative number, so the assumption that $a_3^e=a_1^e$ is contradicted, and it holds that $a_3^e≠a_1^e$. If it cannot be divided evenly, the assumption that $a_3^e=a_1^e$ contradicts to $a_3^e≠a_1^e$. If $a_3^e=a_1^e$ is next.
$a_1^e=k_1/(k_1-3)$
Since both $a_3^e$ and $a_3^e$ are calculated from the same $a_1^e$. So it is next,
$(3k_1+k_2)/((k_2-3^2 ) )=k_1/((k_1-3) )$
If the left side can be divided evenly, the right side should also be able to be divided evenly. It can be calculated as follows.
$(3k_1+k_2 )(k_1-3)=k_1 (k_2-3^2 )$
$(3k_1+k_2 ) k_1-3(3k_1+k_2 )=k_1 k_2-3^2 k_1$
$3k_1 k_1+k_2 k_1-3^2 k_1-3k_2=k_1 k_2-3^2 k_1$
$3k_1 k_1-3k_2=0$ $k_1 k_1=k_2$
Since it is the case that $k_2≥2k_1$
$0≥2k_1-k_1k_1$ $0≥2-k_1$
Because $k≥2$ ,Therefore, the assumption that $a_3^e=a_1^e$ and $a_2^e=a_1^e$ is affirmed, so,
$a_3^e=a_1^e⇒a_2^e=a_1^e$.
The contrapositive of ${\bar{ a_2^e}\bar{=}\bar{a_1^e}} $ ⇒ $(\bar{a_3^e}\bar{=}\bar{a_1^e} )$ is also true, which means that
$a_2^e≠a_1^e ⇒ a_3^e≠a_1^e$.
Conversely, if we assume $a_2^e=a_1^e⇒a_3^e=a_1^e$, The assumption that $a_2^e=a_1^e⇒a_3^e=a_1^e$ as calculated earlier is affirmed.
So, $a_2^e=a_1^e⇒a_3^e=a_1^e$. The contrapositive of ${\bar{ a_2^e}\bar{=}\bar{a_1^e}}⇒ \bar{a_3^e}\bar{=}\bar{a_1^e} $ is also true. So it is $a_3^e≠a_1^e⇒a_32^e≠a_1^e$.
Therefore, it will be like this.
$a_2^e≠a_1^e⇔a_3^e≠a_1^e$
3－3 The relationship between m Cycle and (m-1)Cycle, and the relationship between a Initial value
The relationship between $a_m^e$ and $a_1^e$ is next from the general formula.
$a_m$
$a_m^e= (3^{m-1} a_1^e+3^{m-2}k_1+ 3^{m-3}k_2$
$+ ⋯+3k_{m-2 }+k_{m-1})⁄k_{m-1} $
If $a_m^e=a_1^e$ is next.
$k_{m-1}a_1^e= 3^{m-1} a_m^e+3^{m-2}k_1+ 3^{m-3}k_2$
$+ ⋯+3k_{m-2 }+k_{m-1} $
$(k_{m-1}- 3^{m-1})a_1^e=3^{m-2}k_1+ 3^{m-3}k_2$
$+ ⋯+3k_{m-2 }+k_{m-1} $
Define as,
$3f(m,k_m)=3(3^{m-3}k_1+ 3^{m-4}k_2+ ⋯+k_{m-2})$
$(k_{m-1}- 3^{m-1})a_1^e=3f(m,k_m)+k_{m-1} $
a_1^e= \frac{3f(m,k_m)+k_{m-1}}{k_{m-1}- 3^{m-1}}
If $k_{m-1}<3^{m-1}$, then the right side becomes a negative number, so the assumption that $a_m=a_1$ leads to a contradiction, Thus, it is $a_m≠a_1$.
Also, if the right side cannot be divided evenly, the assumption that $a_m=a_1$ contradicts with $a_m≠a_1$.
If it can be divided evenly, the relationship between $a_{m-1}$ and $a_1$ will be as follows from the general formula.
$a_{m-1}^e= (3^{m-2} a_1^e+3^{m-3}k_1+ 3^{m-4}k_2$
$+ ⋯+3k_{m-3 }+k_{m-2})⁄k_{m-2} $
If $a_{m-1}=a_1$ is next
$(k_{m-2}-3^{m-2})a_{1}^e= (3^{m-3}k_1+ 3^{m-4}k_2$
$+ ⋯+3k_{m-3 }+k_{m-2}) $
a_1^e= \frac{f(m,k_m)}{k_{m-2}-3^{m-2}}
Then the right side becomes a negative number, so the assumption that a_m=a_1 leads to a contradiction, Also, if the right side cannot be divided evenly, the assumption that $a_m=a_1$ contradicts with $a_m≠a_1$.
Because we are calculating with the same $a_1^e$, And so it was
$f(m,k_m )=3^{m-3}k_1+ 3^{m-4}k_2+ ⋯+k_{m-2}$.
It will be as follows.
\frac{f(m,k_m)}{k_{m-2}-3^{m-2}}= \frac{3f(m,k_m)+k_{m-1}}{k_{m-1}- 3^{m-1}}
Since it is assumed that the right side can be divided exactly, the left side should also be able to be divided exactly.
\frac{3f(m,k_m)+k_{m-1}}{k_{m-1}- 3^{m-1}}=2n
Assuming the following,
$3f(m,k_m)+k_{m-1}=2n(k_{m-1}- 3^{m-1})$
$3f(m,k_m)=2n(k_{m-1}- 3^{m-1})-k_{m-1}$
f(m,k_m )=\frac{2n(k_{m-1}- 3^{m-1})-k_{m-1}}{3}
The left side is next.
\frac{2n(k_{m-1}- 3^{m-1})-k_{m-1}}{3}=2n(k_{m-2}-3^{m-2} )
Therefore,
2n(k_{m-1})-k_{m-1}=6n(k_{m-2}-3^{m-2} )+2n 3^{m-1}
(2n-1)k_{m-1}=6n(k_{m-2}-3^{m-2} )+2n3^{m-1}
k_{m-1}=\frac{6n(k_{m-2}-3^{m-2} )+2n3^{m-1}}{(2n-1)}
Since $k_{m-1}≥2k_{m-2}$,
\frac{6n(k_{m-2}-3^{m-2} )+2n3^{m-1}}{(2n-1)}≥2k_{m-2}
6n(k_{m-2}-3^{m-2} )+2n3^{m-1}≥2k_{m-2}(2n-1)
6nk_{m-2}≥4nk_{m-2}-2k_{m-2}
2nk_{m-2}+2k_{m-2}≥0
(2n+2)k_{m-2}≥0
The assumption that $a_{m-1}=a_1$ is affirmed and since $a_m=a_1⇒a_{m-1}=a_1$,
So, $a_m^e=a_1^e⇒a_{m-1}^e=a_1^e$. The contrapositive of ${\bar{ a_{m-1}^e}\bar{=}\bar{a_1^e}}⇒ \bar{a_{m}^e}\bar{=}\bar{a_1^e} $
its contrapositive is also true, so $a_{m-1}^e=a_1^e⇒a_m^e=a_1^e$, which leads to $a_{m-1}^e≠a_1^e⇒a_m^e≠a_1^e$.
As calculated before, the assumption that a_m=a_1 is affirmed, and since $a_{m-1}=a_1⇒a_m=a_1$, the contrapositive is also true, thus $a_m^e=a_1^e⇒a_{m-1}^e=a_1^e$. Therefore, $a_m^e≠a_1^e⇒a_{m-1}^e≠a_1^e$, and after equivalent transformations, we have $a_m^e≠a_1^e⇔a_{m-1}^e≠a_1^e$.
３－４ Result of the Circular Sequence
In section 2-1, it has been proven that $a_2^e≠a_1^e$, in section 2-2 that $a_2^e≠a_1^e⇔a_3^e≠a_1^e$, and in section 2-3 that $a_{m-1}^e≠a_1^e⇔a_m^e≠a_1^e$. Therefore, by mathematical induction, since $a_m^e≠a_1^e$, there are no periodic sequences in the Collatz operation.
4 Encounter with 2 to the power of n
4-1 One Collatz operation as even to even
The general formula by definition is,
$a_2^e=3 a_1^e⁄k_1 +1$
Since $a_1^e⁄k_1$ is divided by 2 until it becomes an odd number, if we set $a_1^e⁄k_1 =2i-1$,
$a_2^e-3(2i-1)=1$ $a_2^e-6i=-2$
The particular solution of the indeterminate equation is,
$10-12=-2$
Subtracting both sides, we get
$a_2^e-10-6i+12=0$ $a_2^e-10=6i-12$
$2(a_2^e⁄2-5)=3(2i-4)$
Since 2 and 3 are prime, we use the variable $g_1$ to,
\left\{ \begin{array}{ll}
a_2^e=6g_1+10 \\
2i=2g_1+4
\end{array} \right.
Therefore, $a_2^e=2^n$,
$2^n=6g_1+10$ $(2^n-10)⁄6=g_1$
$2^n-10=6g_1$ $2^n=6g_1+10$
$g_1=1,9,41,169,⋯→2^n=16,64,256,1024,$⋯
Therefore, there are an infinite number of solutions that result in $a_2^e=2^n$ with a single Collatz operation.
Since $a_1^e⁄k_1 =2i-1$,
$a_1^e⁄k_1 =2(g_1+2)-1=2g_1+3$
$a_1^e=k_1 (2g_1+3)$
Therefore,
$g_1=1,9,41,169,⋯→a_1^e=5k_1,21k_1,85k_1,341k_1$,⋯
Since $5k_1=5×2^j$,
$a_1^e=10,20,40,...$
Similarly, since $21k_1=21×2^j$,
$a_1^e=42,84,168,336,672,1344,...$
Similarly, since $85k_1=85×2^j$,
$a_1^e=85,170,340,680,1,360,⋯$
All of these $a_1^e$ become $2^n$.
4-2 m Collatz calculationsas as even to even
The general formula by definition is,
$a_m^e= (3^{m-1} a_1^e+3^{m-2} k_1+3^{m-3} k_2+⋯+3k_{m-2}+k_{m-1} )⁄k_{m-1}$
Because it is,
$k_{m-1}a_m^e=3^{m-1} a_1^e+3^{m-2} k_1+3^(m-3) k_2+⋯+3k_{m-2}+k_{m-1}$
If so,
$f(m,k_i )=3^{m-2} k_1+3^{m-3} k_2+⋯+3k_{m-2}+k_{m-1}$
$k_{m-1} a_m^e= 3^{m-1} a_1^e+f(m,k_i )$
If $k_{m-1} a_m^e=2^n=2^{p_1-1}$, then according to Fermat's $little^{9)}$,
$2^{p-1}≡ 1(mod p )$
And since the right side is also the same value,
$3^{m-1} a_1^e+f(m,k_i )≡ 1(mod p)$
$3^{m-1} a_1^e+f(m,k_i )-1= (2i-1)p 3^{m-1} a_1^e+f(m,k_i )$
$= (2i-1)p+1$
$3^{m-1} a_1^e+f(m,k_i )-(2i-1)p= 1$
Let $3^{m-1} a_1^e+f(m,k_i )=2x$.
$2x-(2i-1)p= 1$
If p = 3,
$2x-(2i-1)3= 1$ $ 2x-6i+3=1$
$ 2x-6i=-2$
$ 6i-2x=2$
Since it is, the particular solution of the indeterminate equation is $x=5,i=2$.
$12-10=2$
Since it is so, if we subtract both sides,
$6i-12-2x+10= 0$ $6i-12=2x-10$
$3(2i-4)=2(x-5)$
Since 2 and 3 are prime, the general solution can be expressed using the variable $g_1$.
\left\{ \begin{array}{ll}
2i-4=2g_1 \\
x-5=3g_1
\end{array} \right.
\left\{ \begin{array}{ll}
i=g_1+2 \\
x=3g_1+5
\end{array} \right.
If we set the special solution of the indeterminate equation $6i-2x=2$ as $x=2,i=1$, then,
$6-4=2$
Since it is so, if we subtract both sides,
$6i-6-2x+4= 0$ $6i-6=2x-4$
$3(2i-2)=2(x-2)$
Since 2 and 3 are prime, the general solution can be expressed using the variable $g_2$.
\left\{ \begin{array}{ll}
2i-2=2g_2 \\
x-2=3g_2
\end{array} \right.
\left\{ \begin{array}{ll}
i=g_2+1 \\
x=3g_2+2
\end{array} \right.
Since it becomes, the general formula for the special solution $x=5,i=2$.
\left\{ \begin{array}{ll}
2i-4=2g_2 \\
x-5=3g_2
\end{array} \right.
\left\{ \begin{array}{ll}
i=g_2+2 \\
x=3g_2+5
\end{array} \right.
since it is equal to,
\left\{ \begin{array}{ll}
i=g_1+1 \\
x=3g_1+5
\end{array} \right.
$i=g_1+1=g_2+2$ $g_1=g_2+1$
Since $g_1$ and $g_2$ are arbitrary natural numbers, there is no difference due to the difference in particular solutions.
Also, if $p= 5$, then $2x-(2i-1)p= 1$ is,
$2x-(2i-1)5= 1$ $2x-10i+5= 1$ $2x-10i=-4$
$10i-2x=4$
Since it is, the particular solution of the indeterminate equation is $x=3,i=1$.
$10-6=4$
Since it is so, if we subtract both sides,
$10i-10-2x+6= 0$ $10i-10=2x-6$
$5(2i-2)=2(x-3)$
Since $2$ and $5$ are coprime, the general solution uses the variable $g_2$.
\left\{ \begin{array}{ll}
2i-2=2g_2 \\
x-3=5g_2
\end{array} \right.
\left\{ \begin{array}{ll}
i=g_2+1 \\
x=5g_2+3
\end{array} \right.
Let $p=3$, the solution $x=3g_1+5$, and let $p=5$, the solution $x=5g_2+3$.
$3g_1+2=5g_2$ $(3g_1+2)⁄5=g_2$
Since $g_1$ and Encounter with $g_2$ are arbitrary natural numbers, there is no difference due to the difference in the prime number $p$ of $2$. Example: $g_1=1,6,11,⋯:g_2=1,4,7,$⋯
Since we set $3^{m-1} a_1^e+f(m,k_i )=2x$,
$3^{m-1} a_1^e+f(m,k_i )=2(5g_2+3)$
If we set $g_2=4$,
$3^{m-1} a_1^e+f(m,k_i )=2(5×4+3)=46$
$3^(m-1) a_1^e+f(m,k_i )=46$
Let $f(m,k_i )=2l$,
$3^{m-1} a_1^e+2l=46$ $3(3^{m-2} a_1^e )=46-2l$
$3(3^{m-2} a_1^e )=2(23-l)$
Since 2 and 3 are prime, the general solution can be expressed using the variable $g_3$.
\left\{ \begin{array}{ll}
3^{m-2} a_1^e=2g_3 \\
i=3-3g_3
\end{array} \right.
$a_1^e=2g_3⁄3^{m-2}$
Since it is the case, if $g_3=3^{m-2} g_4$,
$a_1^e=2g_4$
Since it becomes so, the differences in the special solutions $x,i$ of each of the indeterminate equations between the two prime numbers $p$ and the differences in the variables $g_i$ used for the general solutions, as well as the differences in m used in the Collatz operation count, are all absorbed by the next variable $g_{i+1}$, and there are no differences resulting from the differences in the values of each variable. Since $a_1^e$ is an arbitrary even natural number, from the calculation result, $3^{m-1} a_1^e+f(m,k_i )≡ 1(mod p)$ must have at least one solution. Therefore, $2^{p-1}≡ 1(mod p)$ is also affirmed, and there is always at least one solution. Therefore, there is at least one solution for all even numbers that results in $a_m^e=2^n$ after $m$ iterations of the Collatz operation. So, the next even number in the Collatz operation converges to 1.
5 Conclusion
In Chapter 2, the general formula for the Collatz operation is defined, in Chapter 3, the absence of cyclic sequences is proven, in Chapter 4, it was proven that all even numbers can be expressed as 2^n. Therefore, the Collatz conjecture has been confirmed.
6 References
1 Von Collatz, L. and Sinogowitz , U, 1957, December. Spektren endlicher Grafen. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (vol. 21, no. 1, pp. 63–77). Springer-
2 Collatz Conjecture. (2021, August 1). In Wikipedia. https://en.wikipedia.org/wiki/Collatz_conjecture
3 Barina, David (2020). “Convergence verification of the Collatz problem”. The Journal of Supercomputing.
4 Terence Tao : Almost all orbits of the Collatz map attain almost bounded values, arXiv:1909.03562v5,15.Feb.2022
5 Li Jiang: The Collatz Conjecture and Linear Indefinite Equation, Turkish Journal of Analysis and Number Theory, 2020, Vol. 8, No. 2, 49-51
6 Baoyuan Duan. A Solution of The Collatz Conjecture Problem, https://doi.org/10.20944/preprints202301.0541.v2
7 Christian Hercher, There are no Collatz m-Cycles with m ≤ 91, Journal of Integer Sequences, Vol. 26 (2023)
8 CHRISTOS R. PAPADIMITRIO, On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, Reprinted from JOURNAL OF COMPUTER AND SYSTEM SCIENCES All Rights Reserved by Academic Press, New York and London, Vol.48, No.3, June !994 Printed in Belgium
9 G.H Hardy , E,M Wright, An Introduction to the Theory of Numbers,1938 Oxford University Press