# «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.

Conclusion

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 [9], [13], [15], [20], [24]. 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 [20], [24]. 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. [5] 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 [14] and Luby [17]. Even though ¿Ü · ½ function iterates possess quite a bit of structure (cf. Garner [11] and Korec [12]) 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 [15] 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 [15] 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 [3] compared this conjecture with predictions derived from one of the branching random walk models of [15]. 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 [4] 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 [1] D. Applegate and J. C. Lagarias, Density Bounds for the ¿Ü · ½ Problem I. TreeSearch Method, Math. Comp. 64 (1995), pp. 411–426.

[2] D. Applegate and J. C. Lagarias, Density Bounds for the ¿Ü · ½ Problem II.

Krasikov Inequalities, Math. Comp. 64 (1995), pp. 427–438.

[3] D. Applegate and J. C. Lagarias, On the Distribution of ¿Ü · ½ Trees, Experimental Math., 4, (1995), pp. 101–117.

[4] K. B. Athreya and P. E. Ney, Branching Processes, Springer-Verlag, New York, 1972.

[5] T. Cloney, C. E. Goles, and G. Y. Vichniac, The ¿Ü · ½ Problem: a Quasi-Cellular Automaton, Complex Systems 1 (1987), pp. 349–360.

[6] 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.

[7] J. H. Conway, Unpredictable Iterations, Proc. 1972 Number Theory Conference, Univ. of Colorado, Boulder, Colorado, 1972, pp. 49–52.

## Ò¸ ´¾Ò ·

[8] C. J. Everett, Iteration of the Number Theoretic Function ´¾Òµ ½µ ¿Ò · ¾, Advances in Math. 25 (1977), pp. 42–45.[9] 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.

[10] Martin Gardner, Mathematical Games, Scientiﬁc American 226 (1972), (June), pp. 114–118.

[11] L. E. Garner, On Heights in the Collatz ¿Ò · ½ Problem, Discrete Math. 55 (1985), pp. 57–64.

[12] I. Korec, The ¿Ü · ½ Problem, Generalized Parcal Triangles, and Cellular Automata, Math. Slovaca, 44 (1994), pp. 85–89.

[13] J. C. Lagarias, The ¿Ü · ½ Problem and Its Generalizations, Amer. Math. Monthly 82 (1985), pp. 3–23.

[14] 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.

[15] J. C. Lagarias and A. Weiss, The ¿Ü · ½ Problem: Two Stochastic Models, Annals Appl. Prob. 2 (1992), pp. 229–261.

[16] G. Leavens and M. Vermeulen, ¿Ü · ½ Search Programs, Computers Math. Appl.

24, No. 11 (1992), pp. 79–99.

[17] M. Luby, Pseudorandomness and Cryptographic Applications, Princeton University Press: Princeton, NJ, 1996.

[18] H. Muller, Das ¿Ò · ½ Problem, Mitteilungen der Math. Ges. Hamburg 12 (1991), pp. 231–251.

[19] T. Oliveira e Silva, Maximum Excursion and Stopping Time Record Holders for the ¿Ü · ½ Problem: Computational Results, Math. Comp., 68, (1999), pp. 371– 384.

[20] D. Rawsthorne, Imitation of an Iteration, Math. Mag. 58 (1985), pp. 172–176.

266 J. C. LAGARIAS [21] R. Terras, A Stopping Time Problem on the Positive Integers, Acta Arithmetica 30 (1976), pp. 241–252.

[22] B. Thwaites, My Conjecture, Bull. Inst. Math. Appl. 21 (1985), pp. 35–41.

[23] V. Vyssotsky, private communication.

[24] S. Wagon, The Collatz Problem, Math. Intelligencer 7 (1985), pp. 72–76.