The ultimate challenge : the 3x+1 problem

The $3x+1$ problem, or Collatz problem, concerns the following seemingly innocent arithmetic procedure applied to integers: If an integer $x$ is odd then ''multiply by three and add one'', while if it is even then ''divide by two''. The $3x+1$ problem asks whether, starting from any positive integer, repeating this procedure over and over will eventually reach the number 1. Despite its simple appearance, this problem is unsolved. Generalizations of the problem are known to be undecidable, and the problem itself is believed to be extraordinarily difficult. This book reports on what is known on this problem. It consists of a collection of papers, which can be read independently of each other. The book begins with two introductory papers, one giving an overview and current status, and the second giving history and basic results on the problem. These are followed by three survey papers on the problem, relating it to number theory and dynamical systems, to Markov chains and ergodic theory, and to logic and the theory of computation. The next paper presents results on probabilistic models for behavior of the iteration. This is followed by a paper giving the latest computational results on the problem, which verify its truth for $x < 5.4 \cdot 10^{18}$. The book also reprints six early papers on the problem and related questions, by L. Collatz, J. H. Conway, H. S. M. Coxeter, C. J. Everett, and R. K. Guy, each with editorial commentary. The book concludes with an annotated bibliography of work on the problem up to the year 2000. The 3x+1 Problem, Or Collatz Problem, Concerns The Following Seemingly Innocent Arithmetic Procedure Applied To Integers: If An Integer X Is Odd Then Multiply By Three And Add One, While If It Is Even Then Divide By Two. The 3x+1 Problem Asks Whether, Starting From Any Positive Integer, Repeating This Procedure Over And Over Will Eventually Reach The Number 1. Despite This Simple Appearance, This Problem Is Unsolved. Generalizations Of The Problem Are Known To Be Undecidable, And The Problem Itself Is Believed To Be Extraordinarily Difficult. This Book Reports On What Is Known On This Problem. It Consists Of A Collection Of Papers, Which Can Be Read Independently Of Each Other. The Book Begins With Two Introductory Papers, One Giving An Overview And Current Status, And The Second Giving The History And Basic Results On The Problem. These Are Followed By Three Survey Papers On The Problem, Relating It To Number Theory, And To Logic And The Theory Of Computation. The Next Paper Presents Results On Probabilistic Models For Behavior Of The Iteration. This Is Followed By A Paper Giving The Latest Computational Results On The Problem. Finally, The Book Reprints Six Early Papers On The Problem And Related Questions. -- From Back Cover. The 3x+1 Problem: An Overview -- The 3x+1 Problem And Its Generalizations / Jeffrey C. Lagarias -- Survey Papers. A 3x+1 Survey: Number Theory And Dynamical Systems / Marc Chamberland -- Generalized 3x+1 Mappings: Markov Chains And Ergodic Theory / K.r. Matthews -- Generalized 3x+1 Functions And The Theory Of Computation / Pascal Michel And Maurice Margenstern -- Stochastic Modelling And Computation Papers. Stochastic Models For The 3x+1 And 5x+1 Problems And Related Problems / Alex V. Kontorovich And Jeffrey C. Lagarias -- Empirical Verification Of The 3x+1 And Related Conjectures / Tomás Oliveira E Silva -- Reprinted Early Papers. Cyclic Sequences And Frieze Patterns (the Fourth Felix Behrend Memorial Lecture) / H.s.m. Coxeter -- Unpredictable Iterations / J.h. Conway -- Iteration Of The Number-theoretic Function: F(2n) = N, F(2n +1) = 3n + 2 / C.j. Everett -- Don't Try To Solve These Problems! / Richard K. Guy -- On The Motivation And Origin Of The (3n + 1)-problem / Lothar Collatz -- Fractran: A Simple Universal Programming Language For Arithmetic / J.h. Conway -- The 3x+1 Problem: An Annotated Bibliography (1963-1999) / Jeffrey C. Lagarias. Jeffrey C. Lagarias, Editor. Includes Bibliographical References And Index. Brings together a collection of articles written about the topic over the last forty years. The articles approach the material from different directions and using different flavours of mathematics, all the while trying to solve the problem.