Lower bounds for the total stopping time of iterates
Authors:
David Applegate and Jeffrey C. Lagarias
Journal:
Math. Comp. 72 (2003), 10351049
MSC (2000):
Primary 11B83; Secondary 11Y16, 26A18, 37A45
Published electronically:
June 6, 2002
MathSciNet review:
1954983
Fulltext 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. Treesearch method, Math. Comp.
64 (1995), no. 209, 411–426. MR 1270612
(95c:11024), http://dx.doi.org/10.1090/S00255718199512706120
 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
(95c:11025), http://dx.doi.org/10.1090/S00255718199512706132
 3.
David
Applegate and Jeffrey
C. Lagarias, The distribution of 3𝑥+1 trees,
Experiment. Math. 4 (1995), no. 3, 193–209. MR 1387477
(97e:11033)
 4.
K. Borovkov and D. Pfeifer, Estimates for the Syracuse problem via a probabilistic model, Theory Probab. Appl. 45 (2000), 300310.
 5.
R.
E. Crandall, On the “3𝑥+1”
problem, Math. Comp. 32
(1978), no. 144, 1281–1292.
MR
0480321 (58 #494), http://dx.doi.org/10.1090/S00255718197804803213
 6.
Jeffrey
C. Lagarias, The 3𝑥+1 problem and its generalizations,
Amer. Math. Monthly 92 (1985), no. 1, 3–23. MR 777565
(86i:11043), http://dx.doi.org/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
(92k:60159)
 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
(93c:11053)
 9.
Tomás
Oliveira e Silva, Maximum excursion and stopping time
recordholders for the 3𝑥+1 problem: computational results,
Math. Comp. 68 (1999), no. 225, 371–384. MR 1613719
(2000g:11015), http://dx.doi.org/10.1090/S0025571899010315
 10.
Daniel
A. Rawsthorne, Imitation of an iteration, Math. Mag.
58 (1985), no. 3, 172–176. MR 789573
(86i:40001), http://dx.doi.org/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
(86d:11103), http://dx.doi.org/10.1007/BF03023011
 13.
Günther
J. Wirsching, The dynamical system generated by the 3𝑛+1
function, Lecture Notes in Mathematics, vol. 1681,
SpringerVerlag, Berlin, 1998. MR 1612686
(99g:11027)
 1.
 D. Applegate and J. C. Lagarias, Density bounds for the problem I. Treesearch method, Math. Comp. 64 (1995), 411426. MR 95c:11024
 2.
 , Density bounds for the problem II. Krasikov inequalities, Math. Comp. 64 (1995), 427438. MR 95c:11025
 3.
 , The distribution of trees, Experimental Math. 4 (1995), 101117. MR 97e:11033
 4.
 K. Borovkov and D. Pfeifer, Estimates for the Syracuse problem via a probabilistic model, Theory Probab. Appl. 45 (2000), 300310.
 5.
 R. E. Crandall, On the ``'' problem, Math. Comp. 32 (1978), 12811292. MR 58:494
 6.
 J. C. Lagarias, The problem and its generalizations, Amer. Math. Monthly 92 (1985), 323. MR 86i:11043
 7.
 J. C. Lagarias and A. Weiss, The problem: Two stochastic models, Ann. Applied Prob. 2 (1992), 229261. MR 92k:60159
 8.
 H. Müller, Das `' Problem, Mitteilungen der Math. Ges. Hamburg 12 (1991), 231251. MR 93c:11053
 9.
 T. Oliveira e Silva, Maximum excursion and stopping time recordholders for the problem: computational results, Math. Comp. 68, No. 1 (1999), 371384. MR 2000g:11015
 10.
 D. W. Rawsthorne, Imitation of an iteration, Math. Mag. 58 (1985), 172176. 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), 7276. MR 86d:11103
 13.
 G. J. Wirsching, The dynamical system generated by the function, Lecture Notes in Math. No. 1681, SpringerVerlag: Berlin 1998. MR 99g:11027
Similar Articles
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 079320971
Email:
david@research.att.com
Jeffrey C. Lagarias
Affiliation:
AT&T Laboratories, Florham Park, New Jersey 079320971
Email:
jcl@research.att.com
DOI:
http://dx.doi.org/10.1090/S0025571802014254
PII:
S 00255718(02)014254
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
