zbMATH — the first resource for mathematics

The \(3x+1\) problem and its generalizations. (English) Zbl 0566.10007
Let \(T(n)=(3n+1)/2\) if \(n\) is odd, \(T(n)=n/2\) if \(n\) is even. The \(3x+1\) conjecture asserts that starting from any positive integer \(n\), repeated iteration of this function eventually produces the value \(1\). The present paper is an excellent survey article of almost all that is currently known about this conjecture. Let us give a brief summary of each section.
Section one is a brief history of the problem, which probably originated with Lothar Collatz in the 1930’s.
For Section two let us define \(\sigma (n)\), the stopping time of \(n\), to be the least positive \(k\) for which \(T^{(k)}(n)<n\) and \(\sigma (n)=\infty\) if no such \(k\) occurs. Most of this section is devoted to a discussion of the work of R. Terras [Acta Arith. 30, 241–252 (1976; Zbl 0348.10037)] of the relation of \(\sigma (n)\) to a similar quantity called the coefficient stopping time of \(n\). It is conjectured that the two quantities are always equal if \(n\geq 2\). Further, proof of this result would show that there are no nontrivial cycles for \(T(n)\). The author shows (Theorem E) that this conjecture is “nearly true”. He also uses his result to bound the number of elements not having a finite stopping time. In the latter part of this section we find a discussion of whether divergent trajectories exist. Here the author shows that if such a trajectory exists it cannot be equidistributed (mod 2). The section concludes with a discussion of the connections of the \(3x+1\) problem to ergodic theory.
In Section 3 the author considers some generalizations of the \(3x+1\) problem, including a discussion of Conway’s result that a related problem is algorithmically undecidable, and how a study of the fractional parts of \((3/2)^ k\) may yield some new results. The paper concludes with a brief discussion of the intractability of the problem and some indication of directions for future research. There is also an excellent collection of 69 references.
All in all, a very fine survey article, very diligently done, and certainly “must” reading for any serious student of the \(3x+1\) problem.

11B83 Special sequences and polynomials
11B37 Recurrences
11-02 Research exposition (monographs, survey articles) pertaining to number theory
11K31 Special sequences
Full Text: DOI