(Terras). The set of integershas 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
The functiondefined 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
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
(Terras). (a) The set of integers with coefficient stopping time k are exactly the set of integers in those congruence classesfor 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
For all,
![]()
where
![]()
Here
is the entropy function and
.
Theorem D cannot be substantially improved; it can be proved that for
any we have