Behavior of the stopping time function.

Contents Next: What is the Up: The 3x+1 problem. Previous: A heuristic argument.

It is Riho Terras's ingenious observation that although the behavior of the total stopping time function seems hard to analyze, a great deal can be said about the stopping time function. He proved the following fundamental result ([67], [68]), also found independently by Everett [31].

Theorem A

(Terras). The set of integers has stopping time has limiting asymptotic density , i.e., the limit

exists. In addition, as , so that almost all integers have a finite stopping time.

The ideas behind Terras's analysis seem basic to a deeper understanding of the problem, so I describe them in detail. In order to do this, I introduce some notation to describe the results of the process of iterating the function . Given an integer n, define a sequence of 0-1 valued quantities by

where

. The results of first k iterations of T are completely described by the parity vector

since the result of k iterations is

where

and

Note that in (2.5), (2.6) both

and

are completely determined by the parity vector

given by (2.3); I sometimes indicate this by writing

(instead of

. The formula (2.4) shows that a necessary condition for

is that

since

is nonnegative. Terras [67] defines the coefficient stopping time

to be the least value of k such that (2.7) holds, and

if no such value of k exists. It is immediate that

The function

plays an important role in the analysis of the behavior of the stopping time function

, see Theorem C.

The formula (2.2) expresses the parity vector

as a function of n. Terra's idea is to reverse this process and express n as a function of

Theorem B

The function defined by

is periodic with period . The induced function is a permutation, and its order is a power of 2.

[Proof]

The cycle structure and order of the first few permutations are given in Table 2. (One-cycles are omitted.) It is interesting to observe that the order of the permutation seems to be much smaller than the upper bound proved in Theorem B. Is there some explanation of this phenomenon?

TABLE 2. Cycle structure and order of permutation

Theorem B allows one to associate with each vector of length k a unique congruence class given by

The integer

with

is the minimal element in

and

is the arithmetic progression:

Now I consider the relation between a vector and stopping times for integers . Define a vector of length k to be admissible if

: (1) ,
: (2) , when .

Note that all admissible vectors of length k have

where

and

denotes the largest integer

. The following result is due to Terras.

Theorem C

(Terras). (a) The set of integers with coefficient stopping time k are exactly the set of integers in those congruence classes for which there is an admissible vector of length k with .
(b) Let for some vector of length k. If is admissible, then all sufficiently large integers congruent to have stopping time k. If is not admissible, then only finitely many integers congruent to have stopping time k.

[Proof]

Theorem C asserts that the set of integers with a given coefficient stopping time k is a set of arithmetic progressions , which has the immediate consequence that has the asymptotic density