Proof of Collatz Conjecture

Abstract

Collatz conjecture (stated in 1937 by Collatz and also named Thwaites conjecture, or Syracuse, 3n+1 or oneness problem) can be described as follows: Take any positive whole number N. If N is even, divide it by 2. If it is odd, multiply it by 3 and add 1. Repeat this process to the result over and over again. Collatz conjecture is the supposition that for any positive integer N, the sequence will invariably reach the value 1. The main contribution of this paper is to present a new approach to Collatz conjecture. The key idea of this new approach is to clearly differentiate the role of the division by two and the role of what we will name here the jump: a = 3n + 1. With this approach, the proof of the conjecture is given as well as informations on generalizations for jumps of the form qn + r and for jumps being polynomials of degree m >1. The proof of Collatz algorithm necessitates only 5 steps: 1- to differentiate the main function and the jumps; 2- to differentiate branches as well as their rst and last terms a and n; 3- to identify that left and irregular right shifts in branches can be replaced by regular shifts in 2m-type columns; 4- to identify the key equation ai = 3ni−1 + 1 = 2m as well as its solutions; 5- to reduce the problem to compare the number of jumps to the number of divisions in a trajectory.