«Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»
The grid consists of 15 lines, a choice of a set of 2 points out of 6, decreased by 2 to account for the loss of the two vertical lines on the left and right sides. In this case, however, we do not count 2 ¢ 13 + 1 = 27 reﬂections but only 19. Indeed, there is a loop and the candidate has to be rejected.
Some results obtained by applying the strategy outlined above are summarized in Figures 7 and 8.
¯ For Æ composite and odd the theoretical maximum of Ê ½ can never be achieved. If no light paths are omitted, Ñ must be 0 for all mirrors, except for E, which has Ñ ½. There will always be an Æ Ò loop, in which Ò stands for any divisor of Æ. For this case a sharper theoretical maximum might be deﬁned, since light paths have to be omitted to account for all Æ Ò loops.
¯ For even Æ this sharper maximum is given by Ê¾. For Æ ¾ to Æ ½, the value Ê¾ can be achieved. Actual solutions for Æ ½ or Æ ¾¼ have not been found, but might be possible.
¯ For Æ there are two solutions; see Figures 7, 8, and 9. For all other Æ up to 16 there is only one solution.
A general solution of the problem has not been found, nor a proof that a solution can always be put on our Æ-grid. It is likely that this is true, since only the Æ-gon grid seems to have a geometry that suits the problem.
One may summarize this by saying that the parity of successive iterates of Ì initially behaves like independent coin ﬂips. Since a number Ò is multiplied by ½ if it is even and approximately ¿ if it is odd, one expects that ¾ ¾ on average it changes multiplicatively by their geometric mean, which is ´ ¿ µ½ ¾. Since this is less than ½, one expects the iterates to decrease in size and eventually become periodic.
Several heuristic probabilistic models describing ¿Ü·½ iterates are based on this idea; see , , , , . The simplest of them assumes that this independent coin-ﬂip behavior persists until ½ is reached under iteration. These mathematical models predict that the expected size of a “random” Ò after steps should be about ´ ¿ µ ¾Ò, so that the average number of steps to reach 1 should be ½ ½
ÐÓ Ò ¾½¾ ÐÓ Ò
´½¿º¾ µ ÐÓ¾¿ Furthermore, the number of steps ½ ´Òµ for Ò to iterate to 1 should be norÔ ¡ ½ mally distributed with mean ½ ÐÓ ¿ ÐÓ Ò and variance ½ ÐÓ Ò, for an ¾ explicit constant ½; see , . There is excellent numerical agreement of this model’s prediction with ¿Ü · ½ function data.
The pseudorandom character of ¿Ü·½ function iterates can be viewed as the source of the difﬁculty of obtaining a rigorous proof of the ¿Ü · ½ Conjecture. On the positive side, Cloney, et al.  proposed using the ¿Ü · ½ function as a pseudorandom number generator. A well-developed theory of pseudorandom number generators shows that even a single bit of pseudorandomness can be inﬂated into an arbitrarily efﬁcient pseudorandom number generator; cf. Lagarias  and Luby . Even though ¿Ü · ½ function iterates possess quite a bit of structure (cf. Garner  and Korec ) they also seem to possess some residual structurelessness, which may be enough for a pseudorandom bit to be extracted.
From this viewpoint it becomes interesting to determine how well the properties of ¿Ü · ½ iterates can be described by a stochastic model. In doing so we are in the atypical situation of modeling a purely deterministic process with a probabilistic model. Here we survey some recent results on stochastic models, obtained in joint work with Alan Weiss and David Applegate, which concern extreme behaviors of ¿Ü · ½ iterates.
Lagarias and Weiss  studied two different stochastic models for the behavior of ¿Ü · ½ function iterates. These models consist of a repeated random walk model for forward iterates by Ì, and a branching random walk model for backward iterates of Ì. The repeated random walk model results of  show almost perfect agreement between empirical data for ¿Ü · ½ function iterates for Ò up to ½¼ ½½. This model has the drawback that 256 J. C. LAGARIAS
Applegate and Lagarias  compared this conjecture with predictions derived from one of the branching random walk models of . The branching process is a multi-type Galton–Watson process with six types labeled 1, 2, 4, 5, 7, 8 pictured in Figure 4. (See Athreya and Ney  for a general discussion of such processes.) The random walk arises from assigning the labels ¼ and ½ to the edges of the resulting tree, where ¼ represents the entering vertex being even and ½ represents the entering vertex being odd; the corresponding random walk 3X + 1 FUNCTION ITERATES 263
References  D. Applegate and J. C. Lagarias, Density Bounds for the ¿Ü · ½ Problem I. TreeSearch Method, Math. Comp. 64 (1995), pp. 411–426.
 D. Applegate and J. C. Lagarias, Density Bounds for the ¿Ü · ½ Problem II.
Krasikov Inequalities, Math. Comp. 64 (1995), pp. 427–438.
 D. Applegate and J. C. Lagarias, On the Distribution of ¿Ü · ½ Trees, Experimental Math., 4, (1995), pp. 101–117.
 K. B. Athreya and P. E. Ney, Branching Processes, Springer-Verlag, New York, 1972.
 T. Cloney, C. E. Goles, and G. Y. Vichniac, The ¿Ü · ½ Problem: a Quasi-Cellular Automaton, Complex Systems 1 (1987), pp. 349–360.
 L. Collatz, On the origin of the ´¿Ò · ½µ Problem (in Chinese), J. of QuFu Normal University, Natural Science Edition, 12, No. 3, (1976), pp. 9–11.
 J. H. Conway, Unpredictable Iterations, Proc. 1972 Number Theory Conference, Univ. of Colorado, Boulder, Colorado, 1972, pp. 49–52.
Ò¸ ´¾Ò · C. J. Everett, Iteration of the Number Theoretic Function ´¾Òµ ½µ ¿Ò · ¾, Advances in Math. 25 (1977), pp. 42–45.
 M. R. Feix, A. Muriel, D. Merlini, and R. Tartani, The ´¿Ü · ½µ ¾ Problem: A Statistical Approach, Proc. 3rd Intl. Conf. on Stochastic Processes, Physics and Geometry-Locarno, 1990.
 Martin Gardner, Mathematical Games, Scientiﬁc American 226 (1972), (June), pp. 114–118.
 L. E. Garner, On Heights in the Collatz ¿Ò · ½ Problem, Discrete Math. 55 (1985), pp. 57–64.
 I. Korec, The ¿Ü · ½ Problem, Generalized Parcal Triangles, and Cellular Automata, Math. Slovaca, 44 (1994), pp. 85–89.
 J. C. Lagarias, The ¿Ü · ½ Problem and Its Generalizations, Amer. Math. Monthly 82 (1985), pp. 3–23.
 J. C. Lagarias, Pseudorandom Number Generators in Cryptography and Number Theory, in: Cryptology and Computational Number Theory, C. Pomerance, ed., Proc. Symp. Appl. Math., Vol. 42, AMS, Providence, R.I. 1990, pp. 115–143.
 J. C. Lagarias and A. Weiss, The ¿Ü · ½ Problem: Two Stochastic Models, Annals Appl. Prob. 2 (1992), pp. 229–261.
 G. Leavens and M. Vermeulen, ¿Ü · ½ Search Programs, Computers Math. Appl.
24, No. 11 (1992), pp. 79–99.
 M. Luby, Pseudorandomness and Cryptographic Applications, Princeton University Press: Princeton, NJ, 1996.
 H. Muller, Das ¿Ò · ½ Problem, Mitteilungen der Math. Ges. Hamburg 12 (1991), pp. 231–251.
 T. Oliveira e Silva, Maximum Excursion and Stopping Time Record Holders for the ¿Ü · ½ Problem: Computational Results, Math. Comp., 68, (1999), pp. 371– 384.
 D. Rawsthorne, Imitation of an Iteration, Math. Mag. 58 (1985), pp. 172–176.
266 J. C. LAGARIAS  R. Terras, A Stopping Time Problem on the Positive Integers, Acta Arithmetica 30 (1976), pp. 241–252.
 B. Thwaites, My Conjecture, Bull. Inst. Math. Appl. 21 (1985), pp. 35–41.
 V. Vyssotsky, private communication.
 S. Wagon, The Collatz Problem, Math. Intelligencer 7 (1985), pp. 72–76.