2010;
344 pp;
Hardcover

MSC: Primary 11; 37;
Secondary 68

Print ISBN: 978-0-8218-4940-8

Product Code: MBK/78

List Price: $62.00

AMS Member Price: $49.60

MAA member Price: $55.80

**Electronic ISBN: 978-1-4704-1813-7
Product Code: MBK/78.E**

List Price: $62.00

AMS Member Price: $49.60

MAA member Price: $55.80

#### Supplemental Materials

# The Ultimate Challenge: The \(3x+1\) Problem

Share this page *Edited by *
*Jeffrey C. Lagarias*

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.

#### Readership

Graduate students and research mathematicians interested in number theory.

#### Reviews & Endorsements

Let me cut to the chase: Lagarias has assembled a fantastic book on a fascinating topic, and it is the type of book that the mathematical community could use more of. The book assembles a variety of articles written about the topic over the last forty years, coming to the material from different directions and using different flavors of mathematics, all in service of trying to solve this problem.

-- MAA Reviews

[This book] contains...two surveys by editor Lagarias...the world's foremost expert. [It also contains] a tremendously useful, richly annotated bibliography...[to] round out the volume. ....A must for all libraries. Highly recommended.

-- D.V. Feldman, Choice

[T]his book is a thorough account of an open and challenging problem.

Overview and introduction

Survey papers

Stochastic modelling and computation papers

Reprinted early papers

Annotated bibliography

[T]his book is a thorough account of an open and challenging problem.

Overview and introduction

Survey papers

Stochastic modelling and computation papers

Reprinted early papers

Annotated bibliography

-- Vincente Muqoz, The European Mathematical Society

#### Table of Contents

# Table of Contents

## The Ultimate Challenge: The $3x+1$ Problem

- Cover Cover11
- Title page iii4
- Epigraph v6
- Contents vii8
- Preface ix10
- Part I. Overview and introduction 116
- The 3π₯+1 problem: An overview 318
- The 3π₯+1 problem and its generalizations 3146
- Part II. Survey papers 5570
- A 3π₯+1 Survey: Number theory and dynamical systems 5772
- Generalized 3π₯+1 mappings: Markov chains and ergodic theory 7994
- Generalized 3π₯+1 functions and the theory of computation 105120
- Part III. Stochastic modelling and computation papers 129144
- Stochastic models for the 3π₯+1 and 5π₯+1 problems and related problems 131146
- Empirical verification of the 3π₯+1 and related conjectures 189204
- Part IV. Reprinted early papers 209224
- Cyclic sequences and Frieze patterns (The Fourth Felix Behrend Memorial Lecture) 211226
- Unpredictable iterations 219234
- Iteration of the number-theoretic function π(2π)=π,π(2π+1)=3π+2 225240
- Donβt try to solve these problems! 231246
- On the motivation and origin of the (3π+1)-problem 241256
- FRACTRAN: A simple universal programming language for arithmetic 249264
- Part V. Annotated bibliography 265280
- The 3π₯+1 problem: An annotated bibliography (1963β1999) 267282
- Back Cover Back Cover1362