Some results on the Collatz problem (Q1587305)

The paper studies iterations of the Collatz function \(f_{\mathcal C}\) given by \(f_{\mathcal C}(n)=n/2\) for even integers \(n\) and \(f_{\mathcal C}(n)=3n+1\) for odd \(n\). Several formulae (theorems 1.1, 2.2-4, 3.4) are given which describe infinite sets of starting integers whose \(f_{\mathcal C}\)-iterates eventually reach \(1\). The method of proof relies on explicit formulae describing the \(f_{\mathcal C}\)-iteration on numbers of special form, e.g., \[ f_{\mathcal C}^{(5k)}\left(3^{2(m-k)}\cdot 2^{3k}\cdot s-5\right) = 3^{2m}\cdot s-5\qquad\text{for \(k=0,1,\ldots,m\).} \] Given positive integers \(k,y\), the authors define the Collatz tree of the root \(y\) \(A(y)=(V,E)\) to consist of the set \(V\) of all positive integers whose \(f_{\mathcal C}\)-iterates include \(y\) as set of vertices, and an edge from vertex \(a\in V\) to vertex \(b\in V\) whenever \(a=f_{\mathcal C}(b)\); it is clear that \(A(y)\) is a tree if \(y\) is not \(f_{\mathcal C}\)-cyclic. A characterisation of ``chain subtrees'' of such a Collatz tree (theorem 2.1) just records well-known results in another fashion. In section 3, a strange conjecture (C) is formulated. Based on some facts concerning the arithmetics of prime residue classes modulo \(3^k\), it is claimed that conjecture (C) can be reformulated as: Let \(g\) be defined on the positive integers as \(g(n)=n/2\) for even \(n\) and \(g(n)=3n-1\) for odd \(n\). Show that, for any positive integer \(n\), there is an integer \(k>0\) such that \(g^{(k)}(n)\leq n\). (This may be called ``finite stopping time conjecture for the \(3n-1\) function''.) To state the results given in section 4, let \(n\) be a vertex of the Collatz tree \(A(8)\), i.e., a positive integer whose \(f_{\mathcal C}\)-iterates eventually reach \(1\). Denote by \(a_n\) the number of \((3x+1)\)-steps and by \(b_n\) the number of \((x/2)\)-steps until 1 is reached. It is shown that the quotient \({a_n\over b_n}\) doesn't have a limit for \(n\to\infty\) (theorem~4.3). Moreover, the following estimates are proved: \({n\cdot 3^{a_n}\over 2^{b_n}}\leq 1\) (theorem 4.4), \({a_n\over b_n}\leq{\log 2\over\log 3}\) (theorem 4.5).