
Contents
Next: The 3x+1 problem.
Up: No Title
Previous: No Title
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-11.gif)
The 3x + 1 problem, also known as the
Collatz problem, the Syracuse problem, Kakutani's problem,
Hasse's algorithm,
and Ulam's problem,
concerns the behavior of the iterates of the function which takes odd
integers n to 3n+1 and even integers n to
.
The 3x+1 Conjecture asserts that, starting from any positive integer
n, repeated iteration of this function eventually produces the value 1.
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-12.gif)
The 3x+1 Conjecture is simple to state and apparently intractably hard
to solve.
It shares these properties with other iteration problems, for example
that of aliquot sequences (see Guy [36], Problem B6)
and with celebrated Diophantine equations such as Fermat's last theorem.
Paul Erdös commented concerning the intractability of the
3x+1 problem: ``Mathematics is not yet ready for such problems.''
Despite this doleful pronouncement, study of the 3x+1 problem has not been
without reward.
It has interesting connections with the Diophantine approximation of
and the distribution
of the sequence
, with questions of ergodic
theory on the 2-adic integers
, and with computability theory ---
a generalization of the 3x+1 problem has been shown to be a computationally
unsolvable problem.
In this paper I describe the history of the
problem and survey all the literature I am aware of
about this problem and its generalizations.
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-13.gif)
The exact origin of the 3x+1 problem is obscure.
It has circulated by word of mouth in the mathematical community for
many years.
The problem is traditionally credited to Lothar Collatz,
at the University of Hamburg. (Click here to see a picture of Collatz.)
In his student days in the 1930's, stimulated by the lectures of
Edmund Landau, Oskar Perron, and Issai Schur,
he became interested in number-theoretic functions.
His interest in graph theory led him to the idea of representing such
number-theoretic functions as directed graphs, and questions about the
structure of such graphs are tied to the behavior of iterates of such
functions [25].
In his notebook dated July 1, 1932, he considered the function
which
gives rise to a permutation P of the natural numbers
He posed the problem of determining the cycle structure of P, and asked in
particular
whether or not the cycle of this permutation containing 8 is
finite or infinite ,
i.e., whether or not the iterates
(8) remain
bounded or are unbounded [24].
I will call the study of the iterates of
the
original Collatz problem.
Although Collatz never published any of his iteration problems,
he circulated them at the International Congress of
Mathematicians in 1950 in Cambridge,
Massachusetts, and eventually the original Collatz problem appeared in
print ([9], [47], [62]).
His original question concerning
(8) has never been answered;
the cycle it belongs to is believed to be infinite.
Whatever its exact origins, the
problem was certainly known to the
mathematical community by the early 1950's; it was
discovered in 1952 by B. Thwaites [72].
(Thanks a lot to Mike Mays, who allows us to include the copy of a two-page
letter written by Collatz where Collatz claims to be first to study the
3x+1 problem. See page 1 and
page 2 of the Collatz letter.
Page 1 also contains a hand-drawn sketch by Collatz.
Here is a sniplet of a letter by Gerner to Collatz on page 2. Special thanks go to Marion Meudt and John
Read, who supplied a translation of the Collatz
letter.)
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-14.gif)
During its travels the
problem has been christened with a variety of names.
Collatz's colleague H. Hasse was interested in the
problem and
discussed generalizations of it with many people, leading to the name
Hasse's algorithm [40].
The name Syracuse problem was proposed by Hasse during a visit to
Syracuse University in the 1950's.
Around 1960, S. Kakutani heard the problem, became interested in it,
and circulated it to a number of people.
He said ``For about a month everybody at Yale worked on it,
with no result.
A similar phenomenon happened when I mentioned it at the University of Chicago.
A joke was made that this problem was part of a conspiracy to slow down
mathematical research in the U.S. [45].''
In this process it acquired the name Kakutani's problem.
S. Ulam also heard the problem and circulated the problem at
Los Alamos and elsewhere, and it is called Ulam's problem
in some circles ([13], [72]).
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-15.gif)
In the last ten years the
problem has forsaken its underground
existence by appearing in various forms as a problem in books and journals,
sometimes without attribution as an unsolved problem.
Prizes have been offered for its solution:
$50 by H. S. M. Coxeter in 1970, then
$500 by Paul Erdös, and more recently
1000 by B. Thwaites [72].
Over twenty research articles have appeared on the
problem and related problems.
![[Annotate]](/organics/icons/sannotate.gif)
![[Shownotes]](../gif/annotate/sshow-16.gif)
In what follows I first discuss what is known about the
problem itself,
and then discuss generalizations of the problem.
I have included or sketched proofs of Theorems B, D, E, F, M and N
because these results are either new or have not appeared in as sharp a form
previously; the casual reader may skip these proofs.

Contents
Next: The 3x+1 problem.
Up: No Title
Previous: No Title