%0 Journal Article %T The Collatz Problem in the Light of an Infinite Free Semigroup %A Manfred Tr¨¹mper %J Chinese Journal of Mathematics %D 2014 %R 10.1155/2014/756917 %X The Collatz (or ) problem is examined in terms of a free semigroup on which suitable diophantine and rational functions are defined. The elements of the semigroup, called T-words, comprise the information about the Collatz operations which relate an odd start number to an odd end number, the group operation being the concatenation of T-words. This view puts the concept of encoding vectors, first introduced in 1976 by Terras, in the proper mathematical context. A method is described which allows to determine a one-parameter family of start numbers compatible with any given T-word. The result brings to light an intimate relationship between the Collatz problem and the problem. Also, criteria for the rise or fall of a Collatz sequence are derived and the important notion of anomalous T-words is established. Furthermore, the concept of T-words is used to elucidate the question what kind of cycles¡ªtrivial, nontrivial, rational¡ªcan be found in the Collatz problem and also in the problem. Furthermore, the notion of the length of a Collatz sequence is discussed and applied to average sequences. Finally, a number of conjectures are proposed. 1. Introduction The ( ) problem, first posed by Lothar Collatz in 1937, concerns the behavior of natural numbers under the recurrence function for odd and for even . The Collatz conjecture says that, for any natural number, the iteration leads to the trivial cycle 1, 4, 2, 1. Historical accounts of the Collatz problem have been given, for example, by Lagarias [1], Wirsching [2], and others. The application of the Collatz rules to a given start number will always result in a sequence of uniquely determined integers. It will be referred to as the Collatz sequence attached to . Only start numbers which are odd will be considered. This simplifies the arguments while not restricting in any way the generality of the results. We also recall the simple fact that, for all integers inside a Collatz sequence, it holds that , i.e. cannot be divided by . This is so because is in the residue class and divisions by cannot result in a number which has divisor . Integers which have a divisor can occur only either as start numbers or as even ones preceding a start number. Since the Collatz operations have unique inverses, we can also consider a sequence going backwards. However, Collatz backward sequences are not unique because there are branch points. The branch points are the integers satisfying at the same time and . To such , one can either apply the inverse operation or one can multiply it by an even power of (the reason being that %U http://www.hindawi.com/journals/cjm/2014/756917/