(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 .The function defined by is periodic with period . The induced function is a permutation, and its order is a power of 2.
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
Note that all admissible vectors of length k have
where and denotes the largest integer . The following result is due to Terras.(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.
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
which is given by Furthermore Theorem C asserts that the set differs from by a finite set, so that also has an asymptotic density which is the same as that of . Consequently, Theorem C implies the first part of Theorem A, that the set of all integers with stopping time at most k have an asymptotic density given by where Now the formula (2.16) can be used to prove the second part of Theorem A, and in fact to prove the stronger result that approaches 1 at an exponential rate as .For all , where Here is the entropy function and .
Theorem D cannot be substantially improved; it can be proved that for any we have
for all sufficiently large k depending on . Hence for any holds for all sufficiently large k depending on .