help annotate
Contents Next: A heuristic argument. Up: No Title Previous: Introduction

The 3x+1 problem.


The known results on the problem are most elegantly expressed in terms of iterations of the function


One way to think of the problem involves a directed graph whose vertices are the positive integers and that has directed edges from n to . I call this graph the Collatz graph of in honor of L. Collatz [25]. A portion of the Collatz graph of is pictured in Fig. 1. A directed graph is said to be weakly connected if it is connected when viewed as an undirected graph, i.e., for any two vertices there is a path of edges joining them, ignoring the directions on the edges. The Conjecture can be formulated in terms of the Collatz graph as follows.
3x+1 CONJECTURE (First form). The Collatz graph of on the positive integers is weakly connected.

We call the sequence of iterates the trajectory of n. There are three possible behaviors for such trajectories when n > 0.

(i). Convergent trajectory. Some .
(ii). Non-trivial cyclic trajectory. The sequence eventually becomes periodic and
for any .
(iii). Divergent trajectory. .

The Conjecture asserts that all trajectories of positive n are convergent. It is certainly true for n > 1 that cannot occur without some occurring. Call the least positive k for which the stopping time of n, and set if no k occurs with . Also call the least positive k for which the total stopping time of n, and set if no such k occurs. We may restate the Conjecture in terms of the stopping time as follows.
3x+1 CONJECTURE (Second form). Every integer has a finite stopping time.

The appeal of the problem lies in the irregular behavior of the successive iterates . One can measure this behavior using the stopping time, the total stopping time, and the expansion factor defined by

if n has a bounded trajectory and if n has a divergent trajectory. For example n = 27 requires 70 iterations to arrive at the value 1 and

Table 1 illustrates the concepts defined so far by giving data on the iterates for selected values of n.
TABLE 1. Behavior of iterates .

The Conjecture has been numerically checked for a large range of values of n. It is an interesting problem to find efficient algorithms to test the conjecture on a computer. The current record for verifying the Conjecture seems to be held by Nabuo Yoneda at the University of Tokyo, who has reportedly checked it for all [2]. In several places the statement appears that A. S. Fraenkel has checked that all have a finite total stopping time; this statement is erroneous [32].

help annotate
Contents Next: A heuristic argument. Up: No Title Previous: Introduction