The 3x + 1 Problem and Its Generalizations
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 \textit{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.
- Endomorphisms of the shift dynamical system, discrete derivatives, and applications
- The Collatz problem
- On heights in the Collatz 3n+1 problem
- Random sequence generation by cellular automata
- A generalization of Everett's result on the Collatz \(3x+1\) problem
- The \(3x +1\) problem: Two stochastic models
- On consecutive numbers of the same height in the Collatz problem
- On some difference equations with eventually periodic solutions
- Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
- Functional equations associated with congruential functions
- Functional equations connected with the Collatz problem
- On a class of 2-adic functions related to the ``\(3x+1\)-problem
- The autoconjugacy of the \(3x+1\) function.
- Structure theorem for (d,g,h)-maps.
- Frontier between decidability and undecidability: A survey
- Some results on the Collatz problem
- Nonclassical birational models for \(\operatorname{Spec}\mathbb{Q}\)
- A topological approach to the Ulam-Kakutani-Collatz conjecture
- The \(3x+1\) problem: a lower bound hypothesis
- A linear algebra approach to the conjecture of Collatz
- A generalization of the Syracuse algorithm in \({\mathbb{F}}_ q[x]\)
- Injectivity and surjectivity of Collatz functions
- A note on Mignosi's generalization of the \((3X+1)\)-problem
- Progress of iteration theory since 1981
- Statistical properties of an iterated arithmetic mapping
- On the combinatorial structure of \(3N+1\) predecessor sets
- A difference equation with eventually periodic solutions
- The word problem for one-relation monoids: a survey
- Multiplication algorithm based on Collatz function
- An automated approach to the Collatz conjecture
- Arithmetic sequences and blocks of powers of two in the Collatz array
- The Collatz conjecture and the quantum mechanical harmonic oscillator
- Conway's work on iteration
- Sorted fibs in base 3/2
- Collatz conjecture revisited: an elementary generalization
- Novel theorems and algorithms relating to the Collatz conjecture
- Combining dynamic and static slicing for analysing assembler
- Die another day
- On the probabilistic proof of the convergence of the Collatz conjecture
- Visualizing generalized \(3x+1\) function dynamics based on fractal
- The Collatz conjecture in a group theoretic context
- Wildness of iteration of certain residue-class-wise affine mappings
- Tag systems and Collatz-like functions
- A generalization of Dirichlet approximation theorem for the affine actions on real line
- A probabilistic model for the 5\(x\)+1 problem and related maps
- The 3x+1 semigroup
- Criteria of measure-preserving for p^k-Lipschitz mappings
- Generalized inverses and the total stopping times of collatz sequences
- A new statistic for the 3x+1 problem
- The 3x+1 problem and directed graphs.
- Inductive complexity measures for mathematical problems
- The 3n+1-conjecture
- Model-checking \(\mathrm{CTL}^*\) over flat Presburger counter systems
- The 3x+1 Problem: An Overview
- A 3x+1 survey: number theory and dynamical systems
- Stochastic models for the 3x+1 and 5x+1 problems and related problems
- Unpredictable iterations
- Teaching the computer how to discover(!) and then prove(!!) (all by itself(!!!)) analogues of Collatz's notorious 3x + 1 conjecture
- Results on the \(3x+1\) and \(3x+d\) conjectures
- Lower bounds for Z-numbers
- The ultimate challenge. The \(3x+1\) problem
- scientific article; zbMATH DE number 5866417 (Why is no real title available?)
- scientific article; zbMATH DE number 5866431 (Why is no real title available?)
- Global asymptotic stability for minimum-delay difference equations
- Real 3𝑥+1
- A Dual-Radix Approach to Steiner’s 1-Cycle Theorem
- Collatz on the dyadic rationals in \([0.5, 1)\) with fractals: how bit strings change their length under \(3x+1\)
- Exploring the \(3x+1\) problem. I.
- BENFORD'S LAW FOR THE $3x+1$ FUNCTION
- Increasing integer sequences and Goldbach's conjecture
- Periodic solutions to some difference equations over the integers
- Periodicity and boundedness for the integer solutions to a minimum-delay difference equation
- Information: The Algorithmic Paradigm
- A note on some piecewise-linear difference equations with Mersenne-type periodic solutions
- An Undecidable Permutation of the Natural Numbers
- scientific article; zbMATH DE number 3910471 (Why is no real title available?)
- scientific article; zbMATH DE number 3924878 (Why is no real title available?)
- Imitation of an Iteration
- A Note on the 3x + 1 Problem
- Algorithmes pour vérifier la conjecture de Syracuse
- A remark about the density of the orbits of the Collatz permutation
- On the nonexistence of nontrivial small cycles of the \(\mu\) function in \(3x+1\) conjecture
- Iterates of Number Theoretic Functions with Periodic Rational Coefficients (Generalization of the 3x+ 1 Problem)
- scientific article; zbMATH DE number 58307 (Why is no real title available?)
- scientific article; zbMATH DE number 166925 (Why is no real title available?)
- Universal pattern generation by cellular automata
- Maximum excursion and stopping time record-holders for the problem: Computational results
- A prelude to the 3x+1 problem
- Embedding the 3x + 1 Conjecture in a 3x + d Context
- scientific article; zbMATH DE number 566416 (Why is no real title available?)
- scientific article; zbMATH DE number 1740999 (Why is no real title available?)
- scientific article; zbMATH DE number 1114509 (Why is no real title available?)
- A Collatz-type conjecture on the set of rational numbers
- Clusters of integers with equal total stopping times in the 3x+1 problem
- scientific article; zbMATH DE number 6902897 (Why is no real title available?)
- The Collatz problem in the light of an infinite free semigroup
- scientific article; zbMATH DE number 2144365 (Why is no real title available?)
- Some remarks about the Collatz problem
- On the nonexistence of $2$-cycles for the $3x+1$ problem
- The set of rational cycles for the 3x+1 problem
This page was built for publication: The 3x + 1 Problem and Its Generalizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3680903)