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

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

Published electronically:
June 6, 2002

MathSciNet review:
1954983

Full-text PDF

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.**D. Applegate and J. C. Lagarias,*Density bounds for the problem I. Tree-search method*, Math. Comp.**64**(1995), 411-426. MR**95c:11024****2.**-,*Density bounds for the problem II. Krasikov inequalities*, Math. Comp.**64**(1995), 427-438. MR**95c:11025****3.**-,*The distribution of trees,*Experimental Math.**4**(1995), 101-117. MR**97e:11033****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 ``'' problem*, Math. Comp.**32**(1978), 1281-1292. MR**58:494****6.**J. C. Lagarias,*The problem and its generalizations*, Amer. Math. Monthly**92**(1985), 3-23. MR**86i:11043****7.**J. C. Lagarias and A. Weiss,*The problem: Two stochastic models*, Ann. Applied Prob.**2**(1992), 229-261. MR**92k:60159****8.**H. Müller,*Das `' Problem*, Mitteilungen der Math. Ges. Hamburg**12**(1991), 231-251. MR**93c:11053****9.**T. Oliveira e Silva,*Maximum excursion and stopping time record-holders for the problem: computational results,*Math. Comp.**68**, No. 1 (1999), 371-384. MR**2000g:11015****10.**D. W. Rawsthorne,*Imitation of an iteration*, Math. Mag.**58**(1985), 172-176. MR**86i:40001****11.**E. Roosendaal, private communication. See also: On the problem, electronic manuscript, available at`http://personal.computrain.nl/eric/wondrous`**12.**S. Wagon,*The Collatz problem*, Math. Intelligencer**7**(1985), 72-76. MR**86d:11103****13.**G. J. Wirsching,*The dynamical system generated by the function*, Lecture Notes in Math. No. 1681, Springer-Verlag: Berlin 1998. MR**99g:11027**

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:
https://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