Abstract

The Collatz conjecture is a mathematical problem that predicts that any positive integer will eventually converged to 1, if odd numbers is multiplied by 3 and added 1, else even numbers divided by 2. This paper proves the correctness of the Collatz conjecture by formulating bottom-up method from 1 to the opposite direction.

Key Words and Phrases

Collatz Conjecture, Collatz Sequence, Bottom up Method, Group theory.

Introduction

Other forms of the Collatz conjecture [1] explain the bottom-up method by stating that "instead of proving that every positive integer eventually becomes 1, we only need to prove that 1 leads backwards to every positive integer." but it is only a conjecture that it would form a tree, as there is no formulation in which all natural numbers appear once in the tree. The purpose of this paper is to formulate it.

Odd Collatz pairs of shortcut

Every positive odd (x = 2n + 1) has a pair value (y = 3n + 2). As the positive odd numbers are unique, those pairs are also unique.

When n = 0, 1 → 2.
When n = 1, 3 → 5.
When n = 2, 5 → 8.
:

This odd (x) and the pair value (y) together are the Collatz pair (x, y).

If the pair value (y) is even, divide by 2ⁱ (i = 1,2,3...) until it is odd. For example, the 26 in the Collatz pair (17, 26) is 2¹ of 13.　Therefore, it reduces to (1.5x + 0.5)/2ⁱ. However, it loops back to 2 only if x = 1, so it loops in the Collatz pair (1, 2).

If the pair value (y) is odd, so it increases by 1.5 times + 0.5.

Odd-odd Collatz pairs

An example of a Collatz pair with odd y = 1.5x + 0.5 for odd x is

All positive odd numbers with x = 3 + 4n are such. And if the right column of the binary number of x is a consecutive of 1s such as 111₍₂₎, then there is a sequence of odd-odd collatz pairs in odd y too.

Odd-odd collatz pairs will finally form a sequence to one odd-even collatz pair.

Odd-even Collatz pairs

An example of Collatz pairs with odd x and even y = 1.5x + 0.5 is

All positive odd numbers with x = 1 + 4n are such. There is also always a root odd z less than x for even y (all even numbers also have a root odd), except x = 1. All odd numbers starting from 1 branch off from this odd-even Collatz pair.

Initial values 15 to 27, the Collatz pair (5, 8) branches from 8 to 5 or 16.... Also, with initial values 27 and 9663, the Collatz pair (425, 638) branchdes from 638 to 425 or 1276….

Conclusion

Thus, every natural number has a unique roots odd sequence, starting from any initial value will always reach 1 within a finite number of operations, converging on a unique roots odd sequence loop (1→2→1).

If we take the above approach, from (group 1 → 4 → 2) to the next root odd group, the Collatz law that accumulates by generation is the same as the natural number law that accumulates one by one from 1.

References

[1] Collatz conjecture (20 May 2022, at 02:37 UTC). In Wikipedia: The Free Encyclopedia. Retrieved from https://en.wikipedia.org/wiki/Collatz_conjecture

The appendix

Appendix 3. Excel file for creating Collatz table