The Collatz problem (Q1059095)

This is the first of a series of articles in which the author will present the current numerical evidence for various mathematical conjectures. In the present paper the author considers the \(3x+1\) problem or Collatz problem which can be stated as follows: Let f be the function (called the Collatz function) on the positive integers defined by \(f(n)=3n+1\) if n is odd, \(f(n)=n/2\) if n is even. Then for any positive integer n there is a k such that \(f^{(k)}(n)\), the kth iterate of f on n equals 1. As evidence for the truth of this conjecture the author presents the following: 1). Let C(n) be defined on the odd integers by \(C(n)=(3n+1)/2^ s\), where \(2^ s \| 3n+1\). On the assumption that as C is iterated s behaves as it would if it were given probabilistically by \(\Pr ob[s=i]=2^{-i}\) for all positive integers i, then the expected number of iterations required for C to bring n to 1 is approximately 8.003 92 log\({}_{10}n\). Calculations carried out to \(10^ 7\) support this conjecture. 2). Let the first k such that \(f^{(k)}(n)<n\) be called the stopping time of n, and be denoted by \(\sigma^*(n)\). Then a). Unless n is in one of 19 residue classes mod 256, \(\sigma^*(n)<13\). b). The asymptotic density of all n with finite stopping time is 1. [See a paper by \textit{R. Terras}, Acta Arith. 30, 241-252 (1976; Zbl 0348.10037).] c). Under the probability assumption on s the expected value of \(\sigma^*(n)\) is about 9.477 955. Again numerical calculations carried out to \(10^ 9\) strongly support the conjecture. 3). The Collatz problem has been verified numerically for all \(n<3*10^{12}\). Using this result, the probability assumption on s and the unproved conjecture that if n is the smallest element of a nontrivial cycle then the cycle must contain at least \(\sqrt{n}/2\) odd terms, the probability of the existence of a nontrivial cycle is less than \(10^{- 17 000}\).