TCS Journal 2011 Journal Article
The convergence classes of Collatz function
- Livio Colussi
The Collatz conjecture, also known as the 3 x + 1 conjecture, can be stated in terms of the reduced Collatz function R ( x ) = ( 3 x + 1 ) / 2 h (where 2 h is the larger power of 2 that divides 3 x + 1 ). The conjecture is: Starting from any odd positive integer and repeating R ( x ) we eventually get to 1. G k, the k -th convergence class, is the set of odd positive integers x such that R k ( x ) = 1. In this paper an infinite sequence of binary strings s h of length 2 ⋅ 3 h − 1 (the seeds) are defined and it is shown that the binary representation of all x ∈ G k is the concatenation of k periodic strings whose periods are s k, …, s 1. More precisely x = s k, d k, 1 [ n 1 ) … s 1, d k, k [ n k ) where s k, d k, i [ n i ) is the substring of length n i that starts in position d k, i in a sufficiently long repetition of the seed s i. Finally, starting positions d k, i and lengths n i for which s k, d k, 1 [ n 1 ) … s 1, d k, k [ n k ) ∈ G k are defined, thus giving a complete characterization of classes G k.