Lower bounds for the total stopping time of iterates

Authors:
David Applegate and Jeffrey C. Lagarias

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

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

Published electronically:
June 6, 2002

MathSciNet review:
1954983

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The total stopping time of a positive integer is the minimal number of iterates of the function needed to reach the value , and is if no iterate of reaches . It is shown that there are infinitely many positive integers having a finite total stopping time such that The proof involves a search of trees to depth 60, A heuristic argument suggests that for any constant , a search of all trees to sufficient depth could produce a proof that there are infinitely many such that It would require a very large computation to search trees to a sufficient depth to produce a proof that the expected behavior of a ``random'' iterate, which is occurs infinitely often.

**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. MR**1270612**, 10.1090/S0025-5718-1995-1270612-0**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. MR**1270613**, 10.1090/S0025-5718-1995-1270613-2**3.**David Applegate and Jeffrey C. Lagarias,*The distribution of 3𝑥+1 trees*, Experiment. Math.**4**(1995), no. 3, 193–209. MR**1387477****4.**K. Borovkov and D. Pfeifer,*Estimates for the Syracuse problem via a probabilistic model*, Theory Probab. Appl.**45**(2000), 300-310.**5.**R. E. Crandall,*On the “3𝑥+1” problem*, Math. Comp.**32**(1978), no. 144, 1281–1292. MR**0480321**, 10.1090/S0025-5718-1978-0480321-3**6.**Jeffrey C. Lagarias,*The 3𝑥+1 problem and its generalizations*, Amer. Math. Monthly**92**(1985), no. 1, 3–23. MR**777565**, 10.2307/2322189**7.**J. C. Lagarias and A. Weiss,*The 3𝑥+1 problem: two stochastic models*, Ann. Appl. Probab.**2**(1992), no. 1, 229–261. MR**1143401****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. MR**1144786****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. MR**1613719**, 10.1090/S0025-5718-99-01031-5**10.**Daniel A. Rawsthorne,*Imitation of an iteration*, Math. Mag.**58**(1985), no. 3, 172–176. MR**789573**, 10.2307/2689917**11.**E. Roosendaal, private communication. See also: On the 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. MR**769812**, 10.1007/BF03023011**13.**Günther J. Wirsching,*The dynamical system generated by the 3𝑛+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

Email:
jcl@research.att.com

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

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