Lower bounds for the total stopping time of $3x + 1$ iterates

Authors:
David Applegate and Jeffrey C. Lagarias

Journal:
Math. Comp. **72** (2003), 1035-1049

MSC (2000):
Primary 11B83; Secondary 11Y16, 26A18, 37A45

DOI:
https://doi.org/10.1090/S0025-5718-02-01425-4

Published electronically:
June 6, 2002

MathSciNet review:
1954983

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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$, a 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.

- David Applegate and Jeffrey C. Lagarias,
*Density bounds for the $3x+1$ problem. I. Tree-search method*, Math. Comp.**64**(1995), no. 209, 411–426. MR**1270612**, DOI https://doi.org/10.1090/S0025-5718-1995-1270612-0 - David Applegate and Jeffrey C. Lagarias,
*Density bounds for the $3x+1$ problem. II. Krasikov inequalities*, Math. Comp.**64**(1995), no. 209, 427–438. MR**1270613**, DOI https://doi.org/10.1090/S0025-5718-1995-1270613-2 - David Applegate and Jeffrey C. Lagarias,
*The distribution of $3x+1$ trees*, Experiment. Math.**4**(1995), no. 3, 193–209. MR**1387477** - K. Borovkov and D. Pfeifer,
*Estimates for the Syracuse problem via a probabilistic model*, Theory Probab. Appl.**45**(2000), 300–310. - R. E. Crandall,
*On the $“3x+1”$ problem*, Math. Comp.**32**(1978), no. 144, 1281–1292. MR**480321**, DOI https://doi.org/10.1090/S0025-5718-1978-0480321-3 - Jeffrey C. Lagarias,
*The $3x+1$ problem and its generalizations*, Amer. Math. Monthly**92**(1985), no. 1, 3–23. MR**777565**, DOI https://doi.org/10.2307/2322189 - J. C. Lagarias and A. Weiss,
*The $3x+1$ problem: two stochastic models*, Ann. Appl. Probab.**2**(1992), no. 1, 229–261. MR**1143401** - Helmut Müller,
*Das “$3n+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. MR**1144786** - Tomás Oliveira e Silva,
*Maximum excursion and stopping time record-holders for the $3x+1$ problem: computational results*, Math. Comp.**68**(1999), no. 225, 371–384. MR**1613719**, DOI https://doi.org/10.1090/S0025-5718-99-01031-5 - Daniel A. Rawsthorne,
*Imitation of an iteration*, Math. Mag.**58**(1985), no. 3, 172–176. MR**789573**, DOI https://doi.org/10.2307/2689917 - E. Roosendaal, private communication. See also: On the $3x+1$ problem, electronic manuscript, available at http://personal.computrain.nl/eric/wondrous
- Stan Wagon,
*The Collatz problem*, Math. Intelligencer**7**(1985), no. 1, 72–76. MR**769812**, DOI https://doi.org/10.1007/BF03023011 - Günther J. Wirsching,
*The dynamical system generated by the $3n+1$ function*, Lecture Notes in Mathematics, vol. 1681, Springer-Verlag, Berlin, 1998. MR**1612686**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11B83,
11Y16,
26A18,
37A45

Retrieve articles in all journals with MSC (2000): 11B83, 11Y16, 26A18, 37A45

Additional Information

**David Applegate**

Affiliation:
AT&T Laboratories, Florham Park, New Jersey 07932-0971

Email:
david@research.att.com

**Jeffrey C. Lagarias**

Affiliation:
AT&T Laboratories, Florham Park, New Jersey 07932-0971

MR Author ID:
109250

Email:
jcl@research.att.com

Received by editor(s):
February 6, 2001

Received by editor(s) in revised form:
June 7, 2001

Published electronically:
June 6, 2002

Article copyright:
© Copyright 2002
American Mathematical Society