## 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.

### MSC:

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

Zbl 0348.10037
Full Text: