The convergence classes of Collatz function

作者：Colussi Livio^*

来源：Theoretical Computer Science, 2011, 412(39): 5409-5419.

DOI：10.1016/j.tcs.2011.05.056

• Collatz conjecture
• 3n+1 problem

The Collatz conjecture, also known as the 3x + 1 conjecture, can be stated in terms of the reduced Collatz function R(x) = (3x + 1)/2(h) (where 2(h) is the larger power of 2 that divides 3x + 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 is an element of G(k) is the concatenation of k periodic strings whose periods are s(k), ... ,s(1). More precisely x = s(k,dk,1)([n1)) .... S(1,dk,k)([nk)) where S(k,dk,i)([ni)) 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,dk,1)([n1)) ... s(1,dk,k)([nk)) is an element of G(k) are defined, thus giving a complete characterization of classes Gk.

• 出版日期2011-9-9