×

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

Citations:

Zbl 0348.10037
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Image of n under the map n->n/2 if n even, n->3n-1 if n odd.
a(n) = 2*n/3 for n divisible by 3, otherwise a(n) = round(4*n/3). Or, equivalently, a(3*n-2) = 4*n-3, a(3*n-1) = 4*n-1, a(3*n) = 2*n.
The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.
Image of n after 3k iterates of ’3x+1’ map (k large).
Limit of the image of n after 2k iterates of ‘(3x+1)/2’ map as k grows.
Number of halving and tripling steps to reach 1 in ’3x+1’ problem, or -1 if 1 is never reached.
Number of halving steps to reach 1 in ’3x+1’ problem, or -1 if this never happens.
Number of tripling steps to reach 1 from n in ’3x+1’ problem, or -1 if 1 is never reached.
In the ’3x+1’ problem, these values for the starting value set new records for number of steps to reach 1.
Record number of steps to reach 1 in ’3x+1’ problem, corresponding to starting values in A006877.
In the ’3x+1’ problem, these values for the starting value set new records for highest point of trajectory before reaching 1.
Record highest point of trajectory before reaching 1 in ’3x+1’ problem, corresponding to starting values in A006884.
(1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.
Iterate the map in A006369 starting at 8.
Normalized extreme values for ”3x+1” trees of depth n.
Normalized extreme values for ”3x+1” trees of depth n.
Normalized extreme values for ”3x+1” trees of depth n.
Smallest number which requires n^2 steps in the 3x+1 problem.
Triangle in which n-th row gives ascending sequence of numbers derived from the (3x+1) problem, beginning with n. Numbers in one row share the same number of iteration steps required to reach the value of ’1’ when applying the (3x+1) algorithm. Each row terminates with a power of 2.
Irregular triangle of Terras-modified Collatz problem.
Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.
Number of primes in {n, f(n), f(f(n)), ..., 1}, where f is the Collatz function defined by f(x) = x/2 if x is even; f(x) = 3x + 1 if x is odd.
Number of squarefree integers in {n, f(n), f(f(n)), ...., 1}, where f is the Collatz function defined by f(x) = x/2 if x is even; f(x) = 3x + 1 if x is odd.
n sets a record for the number of primes in {n, f(n), f(f(n)), ..., 1}, where f is the Collatz function defined by f(x) = x/2 if x is even; f(x) = 3x + 1 if x is odd.
Number of numbers k which give 1 after applying exactly n iterations of the 3k+1 algorithm (if a number is even, divide it by 2; if it is odd, multiply by 3 and add 1). This total includes numbers k which also give 1 for a smaller number of iterations (i.e., for this sequence we do not assume the algorithm halts when 1 is reached).
Iterate the map in A006369 starting at 4.
Number of different cycles computed with the generalized 3x+1 problem using C=2, B=Cn+m, A=C^m.
Number of partitions of T where T = (3n + 1) if n is even and T=(3n + 1)/2 if n is odd.
a(n) = a(n-1)+ [least square > a(n-1)].
Numbers for which the smallest number of steps to reach 1 in ”3x+1” (or Collatz) problem is a prime.