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].

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