Proof of Collatz Conjecture Using Division Sequence

Masashi Furuta

Independent Scholar, Nankoku City, Japan.

DOI: 10.4236/apm.2022.122009                

Abstract

The purpose of this study is to prove the Collatz conjecture using a theorem proving system. First, the division sequence is defined as an alignment of the number of times division by 2 is performed in the Collatz operation. Then, the star conversion is defined, which is a mapping from a specific division sequence to a division sequence. Here it is important to map to some division sequence, not which division sequence. The important point is that the finite length of the division sequence does not change before and after the star conversion. In theorem proving system, we considered two parallel methods: main-proof is a claim to a computer proposition that has the same meaning as the Collatz conjecture. Theorem proving support system “Idris” was used. Moreover, we sub-proved that the 12 “extended star conversion” are closed to the “Collatz operation”. Egison’s computer algebra system is used for proof. The results of the two methods achieved the goal of proving the Collatz conjecture using a theorem proving system.

Keywords

Collatz Conjecture, Division sequence, Well-Founded Induction, ¹Idris, ²Egison

1. Introduction

1.1. Collatz Conjecture

The Collatz conjecture poses the question: “What happens if one repeats the operations of taking any positive integer n?”

➢ Divide n by 2 if n is even, and

➢ Multiply n by 3 and then add 1 if n is odd.

The Collatz conjecture affirms that “for any initial value, one always reaches 1 (and enters a loop of 1 to 4 to 2 to 1) in a finite number of operations”.

We call “(one) Collatz operation” an operation of performing (3x + 1) on an odd number and dividing by 2 as many times as one can.

The “initial value” is the number on which the Collatz operation is performed. This initial value is called the “Collatz value”.

This study inputs the Collatz conjecture claim into a computer proposition with the same meaning and proves it later.

The main consequences of this problem are described in [1].

Recent efforts to prove this issue include:

“Almost all orbits of the Collatz map attain almost bounded values” [2].

“Using automated reasoning approach by the Carnegie Mellon University research team” [3].

[4] deals with probabilistic proofs; [5] are working on the proof by defining “jump: a = 3n + 1”; [6] is working on a proof using graph theory; [7] uses an algorithmic approach, whereas [8] uses the data science approach to prove Collatz conjecture. [9] [10] [11] [12] [13] describe theorem proving systems, in general.

1.2. Division Sequence and Complete Division Sequence

Definition 1.1. A division sequence is a sequence given by arranging the numbers of division by 2 in each operation when the Collatz operation is continuously performed with a positive odd number, n, as the initial value.

For example, in the case of 9, the arrangement of numbers given by continuously performing 3x + 1, and dividing by 2 provides 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 (stops when 1 is reached).

Therefore, the division sequence of 9 is [2, 1, 1, 2, 3, 4].

The division sequence of 1 is an empty list []. Further, [6] is a division sequence of 21, but [6, 2] and [6, 2, 2]... that repeats the loop of 1 to 4 to 2 to 1 are not division sequences.

When the division sequence is finite, it is equivalent to reaching 1 in a series of Collatz operations.

When the division sequence is infinite, it does not reach 1 in a series of Collatz operations.

It is equivalent to entering a loop other than 4-2-1 or increasing the Collatz value endlessly.

Definition 1.2. A complete division sequence is a division sequence of multiples of 3.

➢ 9[2, 1, 1, 2, 3, 4] is a complete division sequence of 9.

➢ 7[1, 1, 2, 3, 4] is a division sequence of 7.

Definition 1.3. Supposing that only one element exists in the division sequence of n, no Collatz operation can be applied to n.

Theorem 1.1. When the Collatz operation is applied to x in the complete division sequence of x (two or more elements), (some) y and its division sequence are obtained.

Proof: This follows the Collatz operation and definition of a division sequence.

Theorem 1.2. When the Collatz operation is applied to y in the division sequence of y (two or more elements), (some) y and its division sequence are obtained.

Proof: It is self-evident from the Collatz operation and definition of a division sequence.

1.3. One Only Looks at Odd Numbers of Multiples of 3

There is no need to look at even numbers.

By continuing to divide all even numbers by 2, one of the odd numbers is achieved.

Therefore, it is only necessary to check “whether all odd numbers reach 1 by the Collatz operation”.

One only needs to look at multiples of 3.

For a number x that is not divisible by 3, the Collatz inverse operation is defined as obtaining a positive integer by (x × 2^k − 1)/3. Multiple numbers can be obtained using the Collatz reverse operation.

Here, we consider the Collatz reverse operation on x.

The remainder of dividing x by 9 is one of 1, 2, 4, 5, 7, 8, i.e.:

1 × 2⁶ $\equiv$ 1

2 × 2^{5 $\equiv$} 1

4 × 2⁴ $\equiv$ 1

5 × 2¹ $\equiv$ 1

7 × 2² $\equiv$ 1

8 × 2³ $\equiv$ 1 (mod 9)

This indicates that multiplying any number by 2 appropriate number of times provides an even number with a reminder of 1 when divided by 9.

By subtracting 1 from this and dividing by 3, we get an odd number that is a multiple of 3.

Performing the Collatz reverse operation once from x provides an odd number y that is a multiple of 3.

If y reaches 1, then x, which was once given by the Collatz operation of y, also reaches 1. Therefore, the following can be stated.

Theorem 1.3. One only needs to check “whether an odd number that is a multiple of 3 reaches 1 by the Collatz operation”.

2. Star Conversion

A star conversion is defined for a complete division sequence.

A complete division sequence of length, n, is copied to a complete division sequence of length, n or n + 1.

The remainder, which is given by dividing the Collatz valuex by 9 is

x $\equiv$ 3 mod 9

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [6, a_1 − 4, a_2, a_3...] is described as A[6, −4].

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [1, a_1 − 2, a_2, a_3...] is described as B[1, −2].

x $\equiv$ 6 mod 9

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [4, a_1 − 4, a_2, a_3...] is described as C[4, −4].

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [3, a_1 − 2, a_2, a_3...] is described as D[3, −2].

x $\equiv$ 0 mod 9

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [2, a_1 − 4, a_2, a_3...] is described as E[2, −4].

The conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [5, a_1 − 2, a_2, a_3...] is described as F[5, −2].

Furthermore, the conversion to copy a finite or infinite sequence [a_1, a_2, a_3...] to a sequence [a_1 + 6, a_2, a_3...] is described as G[+6].

If the original first term is negative, G[+6] is performed in advance.

Example

117 $\equiv$ 0 (mod 9), 117[5, 1, 2, 3, 4] can be converted to E[2, −4] → 9[2, 5−4, 1, 2, 3, 4] and F[5, −2] → 309[5, 5−2, 1, 2, 3, 4].

Table 1 shows the functions corresponding to each star conversion. The function represents a change in the Collatz value.

Table 1. Star conversion in mod 9.

2.1. Any Complete Division Sequence Is Obtained by Performing a Star Conversion on Any Complete Division Sequence

In Tables 2-8, we consider how the Collatz value changes with each star conversion.

Therefore, for 3 mod 9 described as A[6, −4], the first term of the division sequence 4 or less is excluded.

Table 2. A copies 21 + 288t to [21 + 384t].

The star conversion A for 21[6] replaces [6]-A->[6, 2] with [6]-A->[6]. The Collatz value is 21, and it does not change.

As B[1, −2], sum of which the first term of the division sequence is 2 or less is excluded.

Table 3. B copies 21 + 72t to [3 + 12t].

6 mod 9 described as C[4, −4], sum of which the first term of the division sequence is 4 or less is excluded.

Table 4. C copies 213 + 288t to [69 + 96t].

As D[3, −2], sum of which the first term of the division sequence is 2 or less is excluded.

Table 5. D copies 69 + 72t to [45 + 48t].

0 mod 9 is described as E[2, −4], therefore sum of which the first term of the division sequence is 4 or less is excluded.

Table 6. E copies 117 + 288t to [9 + 24t].

As F[5, −2], sum of which the first term of the division sequence is 2 or less is excluded.

Table 7. F copies 45 + 72t to [117 + 192t].

Table 8. G copies 3 + 6t to [213 + 384t].

It can be seen that any conversion provides copying from 3 + 6t to 3 + 6t'.

2.2. Synthesis

Figure 1 shows the synthesis of each calculated star conversion. Combining all star conversions gives “3 + 6t”.

Figure 1. Star conversion synthesis.

Theorem 2.1. Therefore, any complete division sequence is obtained by performing star conversion on any complete division sequence.

If all complete division sequences have finite lengths, then the Collatz conjecture is true.

3. Extended Star Conversion and Extended Complete Division Sequence

Definition 3.1. The extended star conversion is the conversion in which the star conversion is applied multiple times to the complete division sequence of x excluding the Collatz value x of 3, 9. Table 9 shows the extended star conversion.

Table 9. Extended star conversion.

The extended star conversion copies the initial value from 6t + 3 to 6t' + 3.

Definition 3.2. The extended complete division sequence is the division sequence obtained by performing the extended star conversion.

Elements of the extended complete division sequence can contain 0 or negative values.

Definition 3.3. Set of Collatz value and its division sequence

We call copying from (n, [a, b, ...]) to ((3n + 1)/2^a, [b, ...]) an extended Collatz operation.

Definition 3.4. An extended Collatz division sequence is the division sequence when the Collatz value reaches an (odd number that is not a multiple of 3)/2^r (r ≠ 0) after the extended Collatz operation.

Theorem 3.1. Applying the extended star conversion to a complete division sequence of x other than 3, 9 gives the extended complete division sequence of x'.

Proof: Self-evident from the definition of extended star conversion.

Theorem 3.2. Applying the extended Collatz operation to the extended complete division sequence of x gives the extended division sequence of z or the division sequence of y.

Proof: Suppose the Collatz value after the operation is a natural number y, then the division sequence of y is obtained. Otherwise, the extended division sequence of z is obtained.

Theorem 3.3. Applying the extended Collatz operation to the extended sequence z gives the extended division sequence of z' or the division sequence of y.

Proof: If the Collatz value after the operation is a natural number y, the division sequence of y is obtained. Otherwise, the extended division sequence of z' is obtained.

Figure 2 and Figure 3 summarize Theorems 1-1, 1-2, 3-1, 3-2, and 3-3.

Figure 2. Extended star conversion.

The destinations of Collatz operation and extended star conversion are the same.

Figure 3. Example of extended star conversion.

Taking Collatz value 81 as an example.

Theorem 3.4. Let the Collatz operation of “the Collatz value x” be “the next Collatz value y”. If x does extend star conversion and then extended Collatz operation multiple times, it returns to y.

Machine proof: We provide proof using the Egison’s formula-processing ³function.

4. DivSeq and allDivSeq

4.1. DivSeq

divSeq t is a function that returns a complete division sequence of 6t + 3 using 6t + 3 as the Collatz value. Using CoList, we can take both finite and infinite lengths.

4.2. AllDivSeq

allDivSeq t is a function that returns a complete division sequence of 6t + 3 and all extended complete division sequences of 6t + 3 using 6t + 3 as the Collatz value.

4.3. FirstLimited and AllLimited

FirstLimited is a predicate that indicates that the complete division sequence of 6t + 3 in allDivSeq t has a finite length.

AllLimited is a predicate that indicates that all division sequences in allDivSeq t have finite lengths.

Theorem 4-1. allDivSeq of 3, 9 is FirstLimited.

Proof: This follows as the complete division sequence of 3, 9 has a finite length.

Based on this, the program predicates IsFirstLimited10 and IsFirstLimited01.

The proof to the Collatz conjecture in this study is shown by the fact that the finite lengths of all complete division sequences are reduced to IsFirstLimited10 and IsFirstLimited01.

5. Well-Founded Induction Method

In the proof, the well-founded induction library wfInd is used.

➢ S is a function that gives +1 to a natural number. Z is 0.

➢ [★1]wfInd is an original function of the well-founded induction method. Incorporate the function “step” into the function “wfInd”.

➢ The [★2] step is a user-implemented function. A function rs with the type (y: Nat → LT’: y x → P y) can be used.

➢ [★3] LT’ y x means y < x.

➢ [★4] In each case division,

the proof of LT’ y x is passed to the function rs to give P y.

firstToAll and IsFirstLimited** are applied here to give P x.

6. Proof of Final Theorem

6.1. Base makeLimitedDivSeq

Theorem 6.1.

Machine proof: We prove this using the well-founded induction method and case division.

For the number of each case division:

➢ The number is reduced using rs;

➢ The predicate is converted to AllLimited using firstToAll;

➢ Finally, the predicate and numbers are undone using IsFirstLimitedxx.

Table 10 shows the extended star conversion and the decrease in the Collatz value after conversion (6t + 3 in the table below is n in the source code).

Table 10. Extended star conversion and got smaller.

6.2. Sufficient Condition for FirstToAll

Since FirstLimited (first) is given as an argument, decomposing/combining it gives AllLimited. Figure 4 shows the decomposing/combining from “first” to “AllLimited”.

Figure 4. Decomposing/combining from “first” to “AllLimited”.

Decomposing/combining or creating “AllLimited” from “first” inside a function. The proved function firstToAll performs the following processing. “first” means “FirstLimited for all n”. “suff2_1~6” means “FirstLimited in partial n”. Combine suff2_1~6 to get all2. Combine all2~8, IsAllLimited00 to get AllLimited.

6.3. Proof of Final Theorem limitedDivSeq

Theorem 6.2

Machine proof: Passing firstToAll to makeLimitedDivSeq gives limitedDivSeq.

7. Conclusion

I am pleased to have applied the theorem proving method to the unsolved problem and it was successful. In this study, I proposed a proof of the Collatz conjecture using the theorem proving system. Furthermore, I applied the division sequence and well-founded induction as essential tools for constructing this proof. I strongly believe that this treatise proved the Collatz conjecture because I achieved “theorem proving” as an independent program. Additionally, I aim to use the proposed method of theorem proving.

Acknowledgements

I would like to thank all those who read this paper. I thank Crimson Interactive Pvt. Ltd. (Ulatus)—www.ulatus.jp for their assistance in manuscript translation and editing.

NOTES

¹https://www.idris-lang.org.

²https://www.egison.org/.

³https://github.com/righ1113/collatzProof_DivSeq/blob/master/program3/Extension.egi.

Conflicts of Interest

There are no conflicts of interest to declare.

References

[1]	Lagarias, J.C. (2010) The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society. https://doi.org/10.1090/mbk/078
[2]	Tao, T. (2019) Almost All Orbits of the Collatz Map Attain Almost Bounded Values. https://arxiv.org/pdf/1909.03562.pdf
[3]	Yolcu, E., Aaronson, S. and Heule, M.J.H. (2021) An Automated Approach to the Collatz Conjecture. In: Platzer, A. and Sutcliffe, G., Eds., Lecture Notes in Computer Science, Vol. 12699, Springer, Cham. https://doi.org/10.1007/978-3-030-79876-5_27
[4]	Kamal, B. (2019) On the Probabilistic Proof of the Convergence of the Collatz Conjecture. Journal of Probability and Statistics, 2019, Article ID 6814378. https://doi.org/10.1155/2019/6814378
[5]	Deloin, R. (2019) Proof of Collatz Conjecture. Asian Research Journal of Mathematics, 14, 1-18. https://doi.org/10.9734/arjom/2019/v14i230123
[6]	Sultanow, E., Koch, C., and Cox, S. (2020) Collatz Sequences in the Light of Graph Theory. Universität Potsdam, Potsdam. https://doi.org/10.25932/publishup-44325
[7]	Venkatesulu, M. and Devi Parameswari, C. (2019) Verification of Collatz Conjecture: An Algorithmic Approach Based on Binary Representation of Integers, https://arxiv.org/pdf/1912.05942.pdf
[8]	Koch, C., Sultanow, E. and Cox, S. (2020) Divisions by Two in Collatz Sequences: A Data Science Approach. International Journal of Pure Mathematical Sciences, 21, 1-13. https://doi.org/10.18052/www.scipress.com/IJPMS.21.1
[9]	Gonthier, G. (2005) A Computer-Checked Proof of the Four Colour Theorem. http://audentia-gestion.fr/MICROSOFT/4colproof.pdf
[10]	Hales, T., Adams, M., Bauer, G., Tat Dat, D., Harrison, J., Le Truong, H., Kaliszyk, C., Magron, V., Mclaughlin, S., Thang, N.T., Truong, N.Q., Nipkow, T., Obua, S., Pleso, J., Rute, J., Solovyev, A., Hoai An, T.T., Trung, T.N., Diep, T.T., Urban, J., Ky, V.K. and Zumkeller, R. (2015) A Formal Proof of the Kepler Conjecture. https://arxiv.org/pdf/1501.02155.pdf
[11]	Kaliszyk, C., Urban, J., Michalewski, H. and Olšák, M. (2018) Reinforcement Learning of Theorem Proving. https://arxiv.org/pdf/1805.07563.pdf
[12]	Huang, D., Dhariwal, P., Song, D. and Sutskever, I. (2018) GamePad: A Learning Environment for Theorem Proving. https://arxiv.org/pdf/1806.00608.pdf
[13]	Minervini, P., Bosnjak, M., Rocktäschel, T. and Riedel, S. (2018) Towards Neural Theorem Proving at Scale. https://arxiv.org/pdf/1807.08204.pdf