×

zbMATH — the first resource for mathematics

Lower bounds for the total stopping time of \(3x + 1\) iterates. (English) Zbl 1052.11017
Summary: The total stopping time \(\sigma_{\infty}(n)\) of a positive integer \(n\) is the minimal number of iterates of the \(3x+1\) function needed to reach the value \(1\), and is \(+\infty\) if no iterate of \(n\) reaches \(1\). It is shown that there are infinitely many positive integers \(n\) having a finite total stopping time \(\sigma_{\infty}(n)\) such that \(\sigma_{\infty}(n) > 6.14316 \log n.\) The proof involves a search of \(3x +1\) trees to depth 60, A heuristic argument suggests that for any constant \(\gamma < \gamma_{BP} \approx 41.677647\), search of all \(3x +1\) trees to sufficient depth could produce a proof that there are infinitely many \(n\) such that \(\sigma_{\infty}(n)>\gamma\log n.\) It would require a very large computation to search \(3x + 1\) trees to a sufficient depth to produce a proof that the expected behavior of a “random” \(3x +1\) iterate, which is \(\gamma=\frac{2}{\log 4/3} \approx 6.95212,\) occurs infinitely often.

MSC:
11B83 Special sequences and polynomials
11Y16 Number-theoretic algorithms; complexity
26A18 Iteration of real functions in one variable
37A45 Relations of ergodic theory with number theory and harmonic analysis (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] David Applegate and Jeffrey C. Lagarias, Density bounds for the 3\?+1 problem. I. Tree-search method, Math. Comp. 64 (1995), no. 209, 411 – 426. · Zbl 0820.11006
[2] David Applegate and Jeffrey C. Lagarias, Density bounds for the 3\?+1 problem. II. Krasikov inequalities, Math. Comp. 64 (1995), no. 209, 427 – 438. · Zbl 0820.11006
[3] David Applegate and Jeffrey C. Lagarias, The distribution of 3\?+1 trees, Experiment. Math. 4 (1995), no. 3, 193 – 209. · Zbl 0868.11012
[4] K. Borovkov and D. Pfeifer, Estimates for the Syracuse problem via a probabilistic model, Theory Probab. Appl. 45 (2000), 300-310. · Zbl 0984.60050
[5] R. E. Crandall, On the ”3\?+1” problem, Math. Comp. 32 (1978), no. 144, 1281 – 1292. · Zbl 0395.10013
[6] Jeffrey C. Lagarias, The 3\?+1 problem and its generalizations, Amer. Math. Monthly 92 (1985), no. 1, 3 – 23. · Zbl 0566.10007 · doi:10.2307/2322189 · doi.org
[7] J. C. Lagarias and A. Weiss, The 3\?+1 problem: two stochastic models, Ann. Appl. Probab. 2 (1992), no. 1, 229 – 261. · Zbl 0742.60027
[8] Helmut Müller, Das ”3\?+1”-Problem, Mitt. Math. Ges. Hamburg 12 (1991), no. 2, 231 – 251 (German). Mathematische Wissenschaften gestern und heute. 300 Jahre Mathematische Gesellschaft in Hamburg, Teil 2. · Zbl 0773.11018
[9] Tomás Oliveira e Silva, Maximum excursion and stopping time record-holders for the 3\?+1 problem: computational results, Math. Comp. 68 (1999), no. 225, 371 – 384. · Zbl 0919.11020 · doi:10.1090/S0025-5718-99-01031-5 · doi.org
[10] Daniel A. Rawsthorne, Imitation of an iteration, Math. Mag. 58 (1985), no. 3, 172 – 176. · Zbl 0587.10030 · doi:10.2307/2689917 · doi.org
[11] E. Roosendaal, private communication. See also: On the \(3x+1\) problem, electronic manuscript, available at http://personal.computrain.nl/eric/wondrous
[12] Stan Wagon, The Collatz problem, Math. Intelligencer 7 (1985), no. 1, 72 – 76. · Zbl 0566.10008 · doi:10.1007/BF03023011 · doi.org
[13] Günther J. Wirsching, The dynamical system generated by the 3\?+1 function, Lecture Notes in Mathematics, vol. 1681, Springer-Verlag, Berlin, 1998. · Zbl 0892.11002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.