A Short Elementary Proof of the Unprovability of the Collatz Conjecture

Consider any positive integer n. If n is even, halve it. If n is odd, multiply it by 3 and add 1. This algorithm is then repeated indefinitely. It has been conjectured by Collatz that this process, which is also known as Hasse’s algorithm, eventually reaches 1. A new perspective on this problem is offered by considering Hasse’s algorithm in binary representation. Some important consequences are used to establish that no proof of the Collatz conjecture exists.