Collatz Iterative Trajectories of All Odd Numbers Attain Bounded Values ()
1. Introduction
The 3x + 1 problem, also known as the “Collatz conjecture” or the “Syracuse problem”, is an interesting topic. It is easy to understand, but not yet proved. The 3x + 1 problem has attracted many mathematic lovers including famous scholars [1] - [7] . The problem can be described as follows: Take any odd number, multiply it by 3 and add 1 to make it an even number, divide it by the power of 2 to make it an odd number, and repeat the arithmetic operation, the final result must be 1. The 3x + 1 problem can also be written as: Take any odd number greater than 1, multiply it by 3 and add 1 to make it an even number, divide it by the power of 2 to make it an odd number, and repeat the arithmetic operation, the final result must be less than the original odd number. Documents [1] and [2]
have proved that the necessary condition for
is
and also proved that when
, there are many odd numbers that are also convergent, that is,
, but it has not been proven that all odd numbers are convergent. This paper is based on the Collatz iterative formula
, through the change patterns of
towards
, to prove Collatz iteration convergence, that is, the necessary and sufficient condition for
is
.
2. Collatz Iterative Formula
For any odd number N, multiply by 3 and add 1 to make it an even number is called an odd transformation, and divide by the power of 2 to make it an odd number is called an even transformation. This process can be called an odd-even transformation.
The Collatz algorithm of an odd-even transformation can be written as:
(1.1)
(1.2)
The Collatz algorithm of 2nd odd-even transformations can be written as:
(1.3)
(1.4)
The Collatz algorithm of 3rd odd-even transformations can be written as:
(1.5)
(1.6)
Thus, the Collatz algorithm of nth odd-even transformations can be written as:
(1.7)
(1.8)
Adopt the summation notation [3] :
(1.9)
(1.10)
is the number of times of even transformations with regards to the ith odd transformations, m is the accumulative number of times of even transformations.
So (1.7) can be written as:
(1.11)
is the slope of the Collatz iterative formula,
is the intercept of the Collatz iterative formula.
And (1.8) can be written as:
(1.12)
3. Necessary Conditions for Collatz Iteration Convergence
3.1. Necessary Conditions and the Definition of n-Step Odd Number
Define
as follows:
(2.1)
Substitute Equation (1.11) into Equation (2.1) we can get:
(2.2)
Since
, then the necessary condition for
is [2] :
(2.3)
which is, the slope
is less than 1.
From Equation (2.3) it can be obtained that:
(2.4)
Mark the smallest m that satisfies (2.4) as:
(2.5)
Then it can be found that when
, the odd number N will not
fall into a cycle. If an odd number does not fall into a cycle during the odd and even transformation process, then after n times of odd transformations, m times of even transformations will eventually occur, making Equation (2.5) true [4] .
The odd number N that satisfies Equation (2.5) is called n-step odd number.
Define
as follows:
(2.6)
is a function of n, and its value is greater than 0 and less than 1. The relationship between
and n is shown in Table 1.
Table 1. The relationships among
and n.
3.2. Collatz Iterative Trajectory Vector
In the Collatz iterative trajectory sequence
of n-step odd number N,
are all odd numbers, and
may be an odd number or an even number.
which correspond to the Collatz iterative trajectory sequence is called the Collatz iterative trajectory vector of n-step odd number N, where
and
.
It can be seen that:
The number of types of 1-step odd number less than 22 is 1, and the Collatz iterative trajectory vector is:
(2)
The number of types of 2-step odd number less than 24 is 1, and the Collatz iterative trajectory vector is:
(1, 3)
The number of types of 3-step odd numbers less than 25 is 2, and the Collatz iterative trajectory vectors are:
(1, 1, 3)
(1, 2, 2)
The number of types of 4-step odd numbers less than 27 is 3, and the Collatz iterative trajectory vectors are:
(1, 1, 1, 4)
(1, 1, 2, 3)
(1, 2, 1, 3)
The number of types of 5-step odd numbers less than 28 is 7, and the Collatz iterative trajectory vectors are:
(1, 1, 1, 1, 4)
(1, 1, 1, 2, 3)
(1, 1, 1, 3, 2)
(1, 1, 2, 1, 3)
(1, 1, 2, 2, 2)
(1, 2, 1, 1, 3)
(1, 2, 1, 2, 2)
The number of types of 6-step odd numbers less than 210 is 12, and the Collatz iterative trajectory vectors are:
(1, 1, 1, 1, 1, 5)
(1, 1, 1, 1, 2, 4)
(1, 1, 1, 1, 3, 3)
(1, 1, 1, 2, 1, 4)
(1, 1, 1, 2, 2, 3)
(1, 1, 1, 3, 1, 3)
(1, 1, 2, 1, 1, 4)
(1, 1, 2, 1, 2, 3)
(1, 1, 2, 2, 1, 3)
(1, 2, 1, 1, 1, 4)
(1, 2, 1, 1, 2, 3)
(1, 2, 1, 2, 1, 3)
By analogy, all odd-numbered Collatz iterative trajectory vectors of any number of steps can be constructed.
Assume that the number of n-step odd numbers less than
is q, and its vector is:
, then the number of n + 1-step odd numbers less than
is
.
3.3. The Maximum and Minimum Values of Sn(N) and Their Relationships to n
By substituting the Collatz iterative trajectory vector components of n-step odd numbers into Equation (1.12), the
values of n-step odd numbers can be calculated.
1-step odd numbers can be represented by
, and their
value is:
(2.7)
Note x is a non-negative integer.
2-step odd numbers can be represented by
, and their
value is:
(2.8)
3-step odd numbers can be represented by
or
, and their
values are:
(2.9)
(2.10)
4-step odd numbers can be represented by
,
, or
, and their
values are:
(2.11)
(2.12)
(2.13)
5-step odd numbers can be represented by
,
,
,
,
,
or
, and their
values are:
(2.14)
(2.15)
(2.16)
(2.17)
(2.18)
(2.19)
(2.20)
It can be seen that there are multiple odd numbers that are equal to or greater than 3-step odd number. For the same step but different types of odd number, their
values are different, with
minimum value and maximum value exist.
From Equation (1.12), we can see that when the first
components of the Collatz iterative trajectory vector are 1, and the last component is
, that is, the trajectory vector of the n-step odd number is
then
has the minimum value. Substitute the trajectory vector components into Equation (1.12), we can get:
(2.21)
Based on the value of n, Equation (2.5), and Equation (2.21),
of n-step odd numbers can be calculated. Refer to Table 1.
Based on Equation (2.6), Equation (2.21) can be written as:
(2.22)
When n is large enough, then
(2.23)
Based on Equation (1.12), the trajectory vector components of the maximum
should meet the following conditions:
(2.24)
(2.25)
Substitute the Collatz iterative trajectory vector components that satisfy Equation (2.24) and Equation (2.25) into Equation (1.12), the
can be calculated. Refer to Table 1.
According to statistics,
has a good linear relationship with
.
Figure 1 shows their relationship when n is in the range of 1 - 50, and Figure 2 shows their relationship when n in the range of 1 - 500. The larger the n is, the better the linear relationship is. If the value of n is small, an intercept can be added to the linear regression.
It can be seen from Figure 2.
Figure 1. The relationship between
and
(n is in the range of 1 to 50).
Figure 2. The relationship between
and
(n is in the range of 1 to 500).
(2.26)
Based on (2.23), Equation (2.26) can be written as:
(2.27)
That is, the ratio of
is approximately proportional to n.
4. Necessary and Sufficient Conditions for Collatz Iteration Convergence
4.1. n-Step Odd Number Converges When
From Equation (2.2) we can get:
(3.1)
Substitute Equation (2.21) into Equation (3.1) we can get:
(3.2)
If the iteration is divergent, that is,
, because
is an integer, that is,
, substitute it into Equation (3.2) we can get:
(3.3)
It can be seen that
cannot be less than 0.
If the iteration is cyclic, that is,
, substitute it into Equation (3.2) we can get:
(3.4)
For
, the n-step odd number N can be expressed as:
(3.5)
Substitute Equation (3.5) into (3.4) and arrange it, we can get:
(3.6)
It can be seen from the literature [5] that there is no other solution except
(that is,
). This proves that when
, n-step odd number N(>1) neither diverges nor cycles. That is, for this special n-step odd number, Equation (2.5) is the necessary and sufficient condition for convergence.
4.2. n-Step Odd Number Nnmin Converges
Literature [1] has proven that n-step odd numbers N satisfy Equation (2.5), then there do exist n-step odd numbers
such that
. Now we first prove that for the minimum odd number
of n-step odd numbers, the relationship
is established.
From Equation (2.2) we can get:
(3.7)
Substitute
into the above formula to get:
(3.8)
According to Equation (2.5), the minimum odd number
of n-step odd numbers N (
) can be obtained. Figure 3 shows the relationship between
and
. It can be seen from Figure 3 that
increases spirally as
goes up.
Figure 4 shows the relationship between
and
. It can be seen from Figure 4 that
is always
less than 1 and gets close to 0 as
increases spirally. Therefore,
is neither less than 0 nor equal to 0, but is always greater than 0. That is, the relationship
is established.
4.3. All Odd Numbers Greater Than 1 Converge
It is proved below that all odd numbers N less than 2m satisfy. From Equation (3.7) we can get:
Figure 3. The relationship between
and
(
).
Figure 4. The relationship between
and
(
).
Figure 5. The relationship between
and
(
).
(3.9)
According to Equation (2.24), Equation (2.25) and Equation (2.5), the maximum value
of n-step odd number can be calculated. Figure 5 shows
the relationship between
and
.
As depicted in Figure 5, only when
and
,
, that is,
; in other cases,
is always less than 1, and tends to be close to 0 as
spirals up. From Section 4.2, we can see that
and
are convergent, which proves that
for all odd numbers. Therefore, Collatz conjecture is established, and n-step odd numbers can also be called n-step convergence odd numbers.
5. Conclusions
1) For any odd number N, it will not fall into a cycle when
, then after n times of odd transformations, m times of even transformations will eventually occur, making equation
true.
2) For any odd number N that is greater than 1,
is the
necessary and sufficient condition for Collatz iteration convergence, that is,
.