You are here

The Ultimate Challenge: The 3x+1 Problem

Jeffrey C. Lagarias, editor
Publisher: 
American Mathematical Society
Publication Date: 
2010
Number of Pages: 
344
Format: 
Hardcover
Price: 
59.00
ISBN: 
9780821849408
Category: 
Anthology
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Darren Glass
, on
03/31/2011
]

Choose any positive integer you want.
If the number you chose is even, divide it in half. If it is odd, replace x by 3x+1.
Repeat this process.
Repeat it again.
Keep going.

Eventually, you are almost certain to fall into the cycle 4, 2, 1, 4, 2, 1, 4, 2, 1,… I say “almost certain” because it is an open question whether you will fall into this cycle for any positive integer, but it has been tested for all numbers up to roughly 262 (and I felt pretty confident that the number you chose would fall into this bound).

If you are anything like me then when you first heard this problem, which is known in different circles as “The Collatz Conjecture”, “The 3x+1 Problem”, “The Syracuse Problem” and “The Ulam Problem”, you thought there was no way it could be that hard to prove, and you started playing with it for a few minutes before running into a roadblock or two and realizing that the problem actually is that hard. In fact, I think I have fallen into this “trap” on more than one occasion, because the problem seems so strikingly interesting.

Jeffrey Lagarias must feel the same way that I do, but he has stuck with the problem much longer. In particular, while I have never achieved anything more than a few sheets of papers covered with scribbles that end up in a trash can, Lagarias has written a number of papers on “The 3x+1 Problem and other related problems”, and he is the editor of a new book just published by the AMS on the subject, entitled The Ultimate Challenge: The 3x+1 Problem.

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. Since its introduction to the mathematical community, which is most often attributed to Collatz spreading it by word of mouth in the 1950s, people have used techniques from (among other areas) number theory, dynamical systems, probability theory, stochastic processes, ergodic theory, logic, models of computation, and theoretical computer science. If the 3x+1 Problem strikes your fancy, then I absolutely recommend that you seek out Lagarias’ book in order to learn some more about what other people have done on the problem and how it finds its tentacles spreading throughout mathematics.

The book opens with two introductory papers written by Lagarias himself, including his 1985 article in the American Mathematical Monthly where he first wrote about the question. These give brief reviews of the problem, including information about its history and the current status of some of the more popular approaches to solving it. These are followed by three survey papers, written by Marc Chamberland, Keith Matthews, and Maurice Margenstern & Pascal Michel, which give overviews of the ways that dynamical systems, ergodic theory, and the theory of computation can help us make progress on the problem. Several of these papers also consider generalizations of the 3x+1 problem, either by tinkering with the formula we used to define the question or by considering the problem over algebraic number fields or the p-adic numbers. Even just considering it for negative numbers leads to some interesting mathematics!

The third section of the book has two more technical research papers. The first, written by Lagarias and Alex Kontorovich, looks at stochastic models for the behavior of iterates of the 3x+1 map, and show that in a precise way this map behaves in a probabilistic manner even though it is completely deterministic. The second paper by this section is by Tomas Olivera e Silva and discusses computational approaches to this problem. In particular, this paper discusses some computational verification of predictions that the various stochastic models make, and also verifies the conjecture for numbers up to 5.76 x 1018.

The fourth section of the book collects six papers that are older and mostly of historical interest. These include Coxeter’s 1971 paper which is thought to be the earliest published paper discussing the 3x+1 Problem and two papers by John H. Conway showing that a generalization of the 3x+1 Problem is undecideable and giving a programming language to explore this question. Also included is Richard Guy’s paper “Don’t Try To Solve These Problems!” from a 1983 issue of the American Mathematical Monthly, which discusses four problems that Guy begs the reader not to waste time on — all of which remain unsolved nearly 30 years later. Each of these papers come with notes from Lagarias on their historical context as well as what has happened since their original writing. Finally, Lagarias includes an annotated bibliography, describing the 197 papers that had been written on the subject of The 3x+1 Problem as of 1999. (It is worth noting that he has continued this endeavor, and a bibliography describing the more than 100 papers written in the decade 2000–2009 can be found on the Arxiv.)

In his introduction, Lagarias writes of the 3x+1 Problem that “we should not exclude it from the mathematical universe just because we are unhappy with its difficulty. It is a fascinating and addictive problem.” Paul Erdős famously described the 3x+1 problem as a problem that “mathematics is not yet ready for.” This may still be the case years after Erdős said it, but one can’t help but think that Lagarias’ volume will be a significant help in getting future generations of mathematicians ready.


Darren Glass is an Associate Professor of Mathematics at Gettysburg College. His mathematical interests include number theory, algebraic geometry, and cryptography. He can be reached at dglass@gettysburg.edu.

Overview and introduction

  • J. Lagarias -- The $3x+1$ problem: An overview
  • J. Lagarias -- The $3x+1$ problem and its generalizations

Survey papers

  • M. Chamberland -- A $3x+1$ Survey: Number theory and dynamical systems
  • K. R. Matthews -- Generalized $3x+1$ mappings: Markov chains and ergodic theory
  • P. Michel and M. Margenstern -- Generalized $3x+1$ functions and the theory of computation

Stochastic modelling and computation papers

  • A. V. Kontorovich and J. Lagarias -- Stochastic models for the $3x+1$ and $5x+1$ problems and related problems
  • T. O. e Silva -- Empirical verification of the $3x+1$ and related conjectures

Reprinted early papers

  • H. S. M. Coxeter -- Cyclic sequences and Frieze patterns (The Fourth Felix Behrend Memorial Lecture)
  • J. H. Conway -- Unpredictable iterations
  • C. J. Everett -- Iteration of the number-theoretic function $f(2n)=n,f(2n+1)=3n+2$
  • R. K. Guy -- Don't try to solve these problems!
  • L. Collatz -- On the motivation and origin of the $(3n+1)$-problem
  • J. H. Conway -- FRACTRAN: A simple universal programming language for arithmetic

Annotated bibliography

  • J. Lagarias -- The $3x+1$ problem: An annotated bibliography (1963-1999)