FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 20 | 21 ||

«Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»

-- [ Page 22 ] --

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 reflections 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 defined, 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 flips. 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-flip 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 difficulty 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 inflated into an arbitrarily efficient 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, Scientific 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.

Pages:     | 1 |   ...   | 20 | 21 ||

Similar works:

«1 THE PRICE IS WRONG: CAUSES AND CONSEQUENCES OF ETHICAL RESTRAINT OF TRADE Thomas C. Leonard° 1. Introduction A market transaction requires consensual exchange of goods, services or promises. Consent, unanimous consent, is the key. Both buyer and seller must consent to the deal; both must be empowered to veto the exchange. Transactions that are not fully voluntary in this sense, such as those within firms, which involve an authority relationship, or those, such as forced labor, which coerce,...»

«English Teaching: Practice and Critique September, 2007, Volume 6, Number 2 http://education.waikato.ac.nz/research/files/etpc/2007v6n2rev1.pdf pp. 108-118 Review article: Misson, R., & Morgan, W. (2006). Critical literacy and the aesthetic: Transforming the English classroom. Urbana, Il: NCTE. TERRY LOCKE School of Education, University of Waikato – To finish what I was saying about beauty, said Stephen, the most satisfying relations of the sensible must therefore correspond to the necessary...»

«Exploring How Pervasive Computing Can Support Situated Learning Arianit Kurti, Daniel Spikol, Marcelo Milrad, Martin Svensson, & Oskar Pettersson Center for Learning and Knowledge Technologies (CeLeKT) School of Mathematics and System Engineering, Växjö University, {arianit.kurti, daniel.spikol, marcelo.milrad, martin.svensson, oskar.pettersson}@msi.vxu.se Abstract: Pervasive computing offers new ranges of possibilities when it comes to supporting learning and collaboration. The design of...»

«Developing Liner Service Networks in Container Shipping C´sar Ducruet, Theo Notteboom e To cite this version: C´sar Ducruet, Theo Notteboom. Developing Liner Service Networks in Container Shipping. e Song, D.W. and Panayides, P. Maritime Logistics: A complete guide to effective shipping and port management, Kogan Page, pp.77-100, 2012. halshs-00682949 HAL Id: halshs-00682949 https://halshs.archives-ouvertes.fr/halshs-00682949 Submitted on 27 Mar 2012 HAL is a multi-disciplinary open access...»

«1 Report to Rapport au: Council Conseil 9 December 2015 / 9 décembre 2015 Submitted on October 26, 2015 Soumis le 26 octobre 2015 Submitted by Soumis par: Susan Jones, Acting Deputy City Manager, City Operations/ Directrice municipale adjointe par intérim, Opérations municipales Contact Person Personne ressource: Dan Chenier, General Manager/Directeur général, Parks, Recreation and Cultural Services / Services des parcs, loisirs et culture 613-580-2424 ext/poste 24295,...»

«Suez Crisis 1 Suez Crisis The Suez Crisis, also referred to as the Tripartite Aggression,[1] [2] (Arabic: ‫ﺍﻟﻌﺪﻭﺍﻥ ﺍﻟﺜﻼﺛﻲ ﺃﺯﻣﺔ ﺍﻟﺴﻮﻳﺲ‬‎ ʾAzmat al-Sūwais / al-ʿIdwān al-Thalāthī; French: Crise du canal de Suez; Hebrew: ‫מבצע קדש‬‎ Mivtza' Kadesh Operation Kadesh, or ‫ מלחמת סיני‬Milẖemet Sinai, Sinai War) was an offensive war fought by France, the United Kingdom, and Israel against Egypt beginning on October...»

«THE IMPACTS OF GOODS AND SERVICES TAX (GST) ON MIDDLE INCOME EARNERS IN MALAYSIA MOHD RIZAL PALIL1 MOHD ADHA IBRAHIM 2 Abstract The introduction of GST in Malaysia has called many arguments from various parties including academics, professionals and the nation (would become the taxpayers) on how GST affect goods pricesincrease or decrease. The consumers are worrying of the significant price increases on basic needs when the GST has fully implemented. With the relatively high living costs...»

«Certification Review Project Reviewing the Draft Certification Model: A Case Study in DRC (Goma) 1 September 2014 Report prepared by Jock Baker and Philip Tamminga Table of contents Acknowledgements Introduction 1. Structure of the report 2. Background to the field research 3. The humanitarian context in DRC 4. CARE in the DRC 5. Views of Affected Communities 6. Views of Government Health and Education Staff 7. Views of Other Stakeholders on the Model 8. Alignment with Other Relevant Processes...»

«ACUPUNCTURE AND THYROID DISEASE About thyroid disease Thyroid disease includes hypothyroidism, a clinical consequence of deficient secretion by the thyroid gland, and hyperthyroidism, where overproduction of thyroid hormone leads to a state of thyrotoxicosis, (Weetman 2003). Overt hypothyroidism is diagnosed by a serum thyroid-stimulating hormone (TSH) concentration above the normal reference range and a serum free thyroxine (FT4) concentration below the reference range (BTA 2006). Clinical...»

«Earth Pockets Grades K-4 Lesson Summary Students trace everyday objects back to the natural resources from which they were made and learn how to conserve natural resources and protect animal habitats. Overview In this lesson, students will: • Identify the earth’s natural resources.• Discuss how humans and animals depend on natural resources for survival.• Make Earth Pockets (mobiles) that visually show the connection between everyday products and the natural resources needed to make...»

«The Universal Gate of Bodhisattva Kanzeon (Kannon Gyo / The Lotos Sutra) At that time the Bodhisattva Inexhaustible Intent immediately rose from his seat, bared his right shoulder, pressed his palms together and, facing the Buddha, spoke these words: World Honored One, this Bodhisattva Perceiver of the World's Sounds why is he called Perceiver of the World's Sounds? The Buddha said to Bodhisattva Inexhaustible Intent: Good man, suppose there are immeasurable hundreds, thousands, ten thousands,...»

«A French société anonyme (joint stock company) with share capital of €712,366,974 82, rue Henri Farman – 92130 Issy-les-Moulineaux, France Nanterre Trade and Companies Registry no. 602 036 444 INCREASE IN ACCOR SHARE CAPITAL THROUGH THE ISSUE OF ORDINARY ACCOR SHARES IN CONSIDERATION FOR THE CONTRIBUTION IN KIND OF SHARES IN FRHI HOLDINGS LIMITED Appendix to the report of Accor's Board of Directors to the ordinary and extraordinary meeting of shareholders called on July 12, 2016 In...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.