THE 3x + 1 CONJUGACY MAP

Daniel J. Bernstein, Jeffrey C. Lagarias

19960215

Abstract. The 3x + 1 map T and the shift map S are defined by T (x) = (3x + 1)/2 for x odd, T (x) = x/2 for x even, while S(x) = (x − 1)/2 for x odd, S(x) = x/2 for x even. The 3x + 1 conjugacy map Φ on the 2-adic integers Z_{2} conjugates S to T, i.e., Φ ∘ S ∘ Φ^{−1} = T. The map Φ mod 2^{n} induces a permutation Φ_{n} on Z/2^{n}Z. We study the cycle structure of Φ_{n}. In particular we show that it has order 2^{n−4} for n ≥ 6. We also count 1-cycles of Φ_{n} for n up to 1000; the results suggest that Φ has exactly two odd fixed points. The results generalize to the ax + b map, where ab is odd.

1. Introduction

Canadian Journal of Mathematics 48 (1996), 1154–1169. The 3x + 1 problem concerns iteration of the 3x + 1 function

(1.1)  T (x) = \{ \begin{matrix}(3x + 1)/2 & if x ≡ 1 (mod 2) \\ x/2 & if x ≡ 0 (mod 2) \end{matrix}

on the integers Z. The well-known 3x + 1 Conjecture asserts that, for each positive integer n, some iterate T^{k}(n) equals 1, i.e., all orbits on the positive integers eventually reach the cycle {1, 2}.

The 3x + 1 function (1.1) is defined on the larger domain Z_{2} of 2-adic integers. It is a measure-preserving map on Z_{2} with respect to the 2-adic measure, and it is strongly mixing, so it is ergodic; see [8]. More is true. Let S : Z_{2} → Z_{2} be the 2-adic shift map defined by

(1.2)  S(x) = \{ \begin{matrix}(x − 1)/2 & if x ≡ 1 (mod 2) \\ x/2 & if x ≡ 0 (mod 2); \end{matrix}

i.e., S(∑_{i=0}^{∞} b_{i}2^{i}) = ∑_{i=0}^{∞} b_{i+1}2^{i}, if each b_{i} is 0 or 1. Then T is topologically conjugate to S: there is a homeomorphism Φ : Z_{2} → Z_{2} with

(1.3)  Φ ∘ S ∘ Φ^{−1} = T.

In fact T is metrically conjugate to S: one map Φ satisfying (1.3) preserves the 2-adic measure. Thus T is Bernoulli.

The map Φ is determined by (1.3) up to multiplication on the right by an automorphism of the shift S. It is known that the automorphism group of S is

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11B75.

isomorphic to Z/2Z, with nontrivial element V (x) = −1 − x. (See [6, Theorem 6.9] and the introduction to [3].) We obtain a unique function Φ by adding to (1.3) the side condition Φ(0) = 0. We call Φ the 3x + 1 conjugacy map. This function has been constructed several times, apparently first in [8], where Φ^{−1} is denoted Q_{∞}, and also in [1], [2].

An important property of Φ is that it is solenoidal. Here we say that a function f on Z_{2} is solenoidal if, for every n, it induces a function mod 2^{n}, i.e.,

x ≡ y (mod 2^{n}) ⟹ f(x) ≡ f(y) (mod 2^{n}).

This solenoidal property, together with Φ(0) = 0, implies that

(1.4)  Φ(x) ≡ x (mod 2).

For completeness, we give a self-contained proof that Φ is unique. Let Φ and Φ′ be two invertible functions satisfying (1.3) and (1.4). Write Q and Q′ for their inverses. Then S ∘ Q = Q ∘ T and S ∘ Q′ = Q′ ∘ T, and (1.4) gives Q ≡ Q′ (mod 2). If Q ≡ Q′ (mod 2^{k}) then Q∘T = Q′ ∘T (mod 2^{k}), so S ∘Q ≡ S ∘Q′ (mod 2^{k}). Now S ∘ Q and S ∘ Q′ agree in the bottom k bits, and Q and Q′ agree in the bottom bit, so Q and Q′ agree in the bottom k + 1 bits. Hence Q ≡ Q′ (mod 2^{k+1}). By induction Q ≡ Q′ (mod 2^{k}) for every k, so Q = Q′, so Φ = Φ′.

There is an explicit formula for Φ^{−1} ([8]). Let T^{m} denote the mth iterate of T. Then

(1.5)  Φ^{−1}(x) = ∑_{i=0}^{∞}(T^{i}(x) mod 2)2^{i}.

This implies (1.3) and (1.4), and also shows that Φ^{−1} is solenoidal.

There is also an explicit formula for Φ ([2]). For x ∈ Z_{2}, expand x as

x = ∑_{l} 2^{d_{l}},

in which {d_{l}} is a finite or infinite sequence with 0 ≤ d_{1} < d_{2} < · · ·. Then

(1.6)  Φ(x) = − ∑_{l} 3^{−l}2^{d_{l}}.

This also implies (1.3) and (1.4), and shows that Φ is solenoidal.

Various properties of the 3x + 1 map under iteration can be formulated in terms of properties of Φ. The 3x + 1 Conjecture is reformulated as follows ([2], [8]). Here Z^{+} denotes the positive integers.

3x + 1 Conjecture. Z^{+} ⊆ Φ(\frac{1}{3}Z).

Furthermore, it is known that Φ(Q ∩ Z_{2}) ⊆ Q ∩ Z_{2}. (This is easily proven from (1.6); see [2].) The following conjecture is proposed in [8].

Periodicity Conjecture. Φ(Q ∩ Z_{2}) = Q ∩ Z_{2}.

This would imply that the 3x + 1 function T has no divergent trajectories on Z. Recall that a trajectory {T^{k}(n) : k ≥ 1} is divergent if it contains an infinite number of distinct elements, so that |T^{k}(n)| → ∞ as k → ∞. In fact, if

T_{3,k}(x) = \{ \begin{matrix}(3x + k)/2 & if x ≡ 1 (mod 2), \\ x/2 & if x ≡ 0 (mod 2), \end{matrix}

then the Periodicity Conjecture is equivalent to the assertion that, for all k ≡ ±1 (mod 6), the 3x + k function has no divergent trajectories on Z. (This follows from [9, Corollary 2.1b].)

This paper studies the 3x + 1 conjugacy map Φ for its own sake. The function Φ is a solenoidal bijection; it induces permutations Φ_{n} of Z/2^{n}Z. Our object is to determine properties of the cycle structure of the permutations Φ_{n}. In effect, our results give information about the iterates Φ^{k} of Φ. We prove in particular that Φ_{n} contains three “long” cycles of length 2^{n−4}, for all n ≥ 6.

We remark that the results we prove are not related to the 3x + 1 Conjecture in any immediate way; indeed for the iterates T^{k} the conjugacy (1.3) gives Φ ∘ S^{k} ∘ Φ^{−1} = T^{k}, a relation which does not involve Φ^{k} for any k ≥ 2. We do note that the Periodicity Conjecture is equivalent, for any k ≥ 1, to the assertion that Φ^{k}(Q ∩ Z_{2}) = Q ∩ Z_{2}. Consequently information about Φ^{k} may conceivably prove useful in resolving the Periodicity Conjecture.

The contents of the paper are as follows. In §2 we give a table of the cycle lengths of Φ_{n} for n ≤ 20. This table motivated our results. We also give data on 1-cycles of Φ_{n} for n ≤ 1000. We conjecture that Φ has exactly two odd fixed points. In §3 we formulate results on the progressive stabilization of the “long” cycles of Φ_{n}. In §4 we generalize these results to the conjugacy map for the ax + b function

T_{a,b}(x) = \{ \begin{matrix}(ax + b)/2 & if x ≡ 1 (mod 2) \\ x/2 & if x ≡ 0 (mod 2), \end{matrix}

where ab is odd. We prove all these results in §5. The proofs are based on Theorem 5.1, which keeps track of the highest-order significant bit in the orbit of x mod 2^{n+2}. In §6 we reconsider “short” cycles of Φ_{n}, and present a heuristic argument that relates their asymptotics to the number of global periodic points. This heuristic is consistent with the data on 1-cycles presented in §2.

There are two appendices on solenoidal maps. Appendix A shows the equivalence of “solenoidal bijection,” “solenoidal homeomorphism,” and “2-adic isometry.” Appendix B shows that a wide class of functions U generalizing the 3x + 1 map T are conjugate to the 2-adic shift S by a solenoidal conjugacy map Φ_{U}.

Finally, we note that, for odd k, the map Q(x) = kx conjugates the 3x + 1 function to the 3x + k function; i.e., Q ∘ T ∘ Q^{−1} = T_{3,k}. Thus the cycle structure of the permutations mod 2^{n} of all the conjugacy maps Φ_{3,k} are identical. Other properties of the 3x + 1 conjugacy map appear in [2], [10], [11]. In particular, Φ and Φ^{−1} are nowhere differentiable on Z_{2}; see [10], [2].

We thank Mike Boyle and Doug Lind for supplying references concerning the automorphism group of the one-sided shift, and the referee for helpful comments.

2. Empirical Data and Two Conjectures

By (1.4), Φ_{n} takes odd numbers to odd numbers. Let Φ̂_{n} : (Z/2^{n}Z)^{∗} → (Z/2^{n}Z)^{∗} denote its restriction. The properties of Φ_{n} are completely determined by Φ̂_{n}. Indeed, Φ(2^{j}x) = 2^{j}Φ(x) by (1.6), so the action of Φ̂_{n−j} describes the action of Φ_{n} on odd numbers times 2^{j}.

Each Φ̂_{n} consists of cycles of various lengths, all of which are powers of 2. (See §3 for a proof.) The exact form of Φ̂_{n} for n ≤ 6 appears in Table 2.1.

n  Φ̂_{n}  order(Φ̂_{n})
2  identity  1
3  {1, 5}  2
4  {1, 5} {9, 13}  2
5  {1, 21} {5, 17} {7, 23} {9, 29, 25, 13}  4
6  {1, 21} {3, 35} {5, 17, 37, 49} {7, 23} {9, 29, 25, 13}
{19, 51} {27, 59} {33, 53} {39, 55} {41, 61, 57, 45}  4

Table 2.1. Cycle structure of Φ̂_{n}, n ≤ 6. 1-cycles are omitted.

Table 2.2 below lists the number of cycles of various lengths in Φ̂_{n} for n ≤ 20. Let X_{n,j} denote the set of cycles of Φ̂_{n} of period 2^{j}, and let |X_{n,j}| be the number of such cycles. From Table 2.2 we see, empirically, that

(2.1)  order(Φ̂_{n}) = 2^{n−4},  n ≥ 6.

We also see a progressive stabilization of the number of “long” cycles in Φ̂_{n}. In §3–§5 we prove both these facts.

How does |X_{n,j}|, the number of cycles of Φ̂_{n} of size 2^{j}, behave as n → ∞, for fixed j? We give data for the simplest case |X_{n,0}| of 1-cycles. Table 2.3 gives all values of |X_{n,0}| for n ≤ 100, and Table 2.4 gives values of |X_{n,0}| at intervals of 10 for n ≤ 1000. We computed the values |X_{n,0}| recursively for increasing n by tracking each 1-cycle individually.

(k, j)  0 1 2 3 4 5 6 7 8 9
1  12 32 52 80 116 106 152 124 110
2  2 16 38 54 82 122 112 144 124 108
3  2 26 36 56 96 124 110 120 130 108
4  4 22 38 54 106 124 112 108 128 92
5  6 18 36 54 116 114 106 114 128 96
6  6 20 36 54 90 128 92 132 136 96
7  8 18 50 68 82 118 106 140 124 102
8 14 12 60 68 92 94 116 144 118 108
9 14 16 62 84 102 92 122 144 104 88
10 10 26 50 92 108 100 132 144 98 90

Table 2.3. Number of 1-cycles in Φ̂_{10j+k}.

(n, j) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 2
3 2 1
4 4 2
5 6 3 1
6 6 7 3
7 8 10 3 3
8 14 17 8 0 3
9 14 21 18 4 0 3
10 10 35 24 14 2 0 3
11 12 40 37 18 12 2 0 3
12 16 48 70 23 16 10 2 0 3
13 26 53 79 60 24 11 10 2 0 3
14 22 63 111 98 50 14 11 10 2 0 3
15 18 81 129 153 84 40 11 11 10 2 0 3
16 20 96 179 186 137 78 31 11 11 10 2 0 3
17 18 91 242 236 207 131 61 29 11 11 10 2 0 3
18 12 104 305 308 312 192 105 56 29 11 11 10 2 0 3
19 16 86 375 401 432 307 152 99 54 29 11 11 10 2 0 3
20 26 95 424 573 564 445 281 133 91 54 29 11 11 10 2 0 3

Table 2.2. Number of cycles |X_{n,j}| of Φ̂_{n} of order 2^{j}, 0 ≤ j ≤ n.

\begin{matrix}(k, j) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 10 & 96 & 380 & 700 & 844 & 1278 & 1078 & 1330 & 1944 & 2030 \\ 2 & 26 & 90 & 458 & 788 & 840 & 1176 & 1130 & 1142 & 2180 & 2162 \\ 3 & 50 & 116 & 452 & 916 & 1134 & 1000 & 1212 & 1170 & 2194 & 2230 \\ 4 & 92 & 156 & 544 & 780 & 942 & 914 & 1270 & 1240 & 2226 & 2128 \\ 5 & 108 & 240 & 574 & 678 & 874 & 998 & 1462 & 1346 & 2130 & 2206 \\ 6 & 100 & 278 & 588 & 908 & 910 & 1110 & 1476 & 1538 & 2294 & 2362 \\ 7 & 132 & 282 & 628 & 818 & 866 & 1172 & 1360 & 1562 & 2204 & 2354 \\ 8 & 144 & 320 & 634 & 784 & 932 & 1172 & 1358 & 1778 & 2184 & 2362 \\ 9 & 98 & 378 & 784 & 870 & 1060 & 1072 & 1190 & 1974 & 2114 & 2242 \\ 10 & 90 & 404 & 714 & 892 & 1150 & 1086 & 1208 & 1808 & 2056 & 2308 \end{matrix}

Table 2.4. Number of 1-cycles in Φ̂_{100j+10k}.

The tables show that |X_{n,0}| behaves irregularly, but has a general tendency to increase. In §6 we present a heuristic model which suggests that

(2.2)  |X_{n,0}| ∼ F_{0}n  as  n → ∞,

where F_{0} is the number of odd fixed points of Φ. Comparison with Table 2.4 suggests the following conjecture.

Fixed Point Conjecture. The 3x + 1 conjugacy map Φ has exactly two odd fixed points.

We searched for odd rational fixed points, and immediately found two: x = −1 and x = 1/3. The conjecture thus asserts that these are the only odd fixed points of Φ. We do not know of any approach to determine the existence or non-existence of non-rational odd fixed points.

More generally we propose the following conjecture.

3x+1 Conjugacy Finiteness Conjecture. For each j ≥ 0, the 3x+1 conjugacy map Φ has finitely many odd periodic points of period 2^{j}.

We have no idea whether the 3x + 1 conjugacy map Φ has finitely many odd periodic points in total. There are examples of ax + b conjugacy maps that have no odd periodic points; see §4.

3. Cycle structure of Φ_{n}: Inert Cycles and Stable Cycles

There is a simple relation between the cycles of Φ_{n} and those of Φ_{n+1}: For x ∈ Z_{2}, the cycle σ_{n+1}(x) that x belongs to in Φ_{n+1} has length |σ_{n+1}(x)| either equal to or double the length of the cycle σ_{n}(x) that x belongs to in Φ_{n}.

This follows from a more general fact. Call a function f_{n+1} : Z/m^{n+1}Z → Z/m^{n+1}Z consistent mod m^{n} if it induces a function f_{n} from Z/m^{n}Z to Z/m^{n}Z, i.e., if

(3.1)  x_{1} ≡ x_{2} (mod m^{n}) ⟹ f_{n+1}(x_{1}) ≡ f_{n+1}(x_{2}) (mod m^{n}).

Lemma 3.1. Let f_{n+1} : Z/m^{n+1}Z → Z/m^{n+1}Z be a function which is consistent mod m^{n}. If x is a purely periodic point of f_{n+1} then x is a purely periodic point of f_{n} and

|σ_{n+1}(x)| = k |σ_{n}(x)|

for some integer k with 1 ≤ k ≤ m.

Proof. The image of σ_{n+1}(x) under projection mod m^{n} consists of k copies of a purely periodic orbit σ_{n}(x), for some k ≥ 1. The bound k ≤ m follows because any element of Z/m^{n}Z has only m distinct preimages in Z/m^{n+1}Z. □

Lemma 3.1 applies to Φ_{n+1}, because Φ is solenoidal. Since m = 2 we have

|σ_{n+1}(x)| = k |σ_{n}(x)|  with  k = 1 or 2.

We call a cycle σ_{n+1}(x) split if |σ_{n+1}(x)| = |σ_{n}(x)|, because σ_{n}(x) lifts to two cycles mod 2^{n+1}, namely σ_{n+1}(x) and σ_{n+1}(x) + 2^{n}. If |σ_{n+1}(x)| = 2 |σ_{n}(x)| we call σ_{n+1}(x) inert, because σ_{n}(x) has lifted to a single cycle. If σ_{n+1}(x) is an inert cycle, and |σ_{n}(x)| = p, then |σ_{n+1}(x)| = 2p and

(3.2)  Φ_{n+1}^{p}(x) ≡ x + 2^{n} (mod 2^{n+1}).

By induction on n, the length of any cycle |σ_{n}(x)| is a power of 2.

We call a cycle σ_{n}(x) stable if σ_{m}(x) is an inert cycle for all m ≥ n. If σ_{n}(x) is a stable cycle, then

|σ_{m}(x)| = 2^{m−n+1} |σ_{n−1}(x)| , m ≥ n.

For a stable cycle σ_{n}(x), Lemma 3.1 guarantees that the map Φ restricted to

{y ∈ Z_{2} : y ≡ x_{i} (mod 2^{n}) for some x_{i} ∈ σ_{n}(x)}

has no periodic points.

Our main result concerning Φ is as follows.

Theorem 3.1. For the 3x + 1 conjugacy map Φ, suppose that |σ_{n}(x)| ≥ 4 and that σ_{n}(x) and σ_{n+1}(x) are both inert cycles. Then σ_{n+2}(x) is also an inert cycle. Consequently σ_{n}(x) is a stable cycle.

Theorem 3.1 follows from Corollary 5.1 at the end of §5.

The hypothesis |σ_{n}(x)| ≥ 4 is necessary in Theorem 3.1. For example, σ_{5}(3) = {3}, so both σ_{6}(3) = {3, 35} and σ_{7}(3) = {3, 99, 67, 35} are inert, but σ_{8}(3) = {3, 227, 195, 163} is split.

Corollary 3.1a. order(Φ̂_{n}) = order(Φ_{n}) = 2^{n−4}, for n ≥ 6.

Proof. σ_{6}(5) = {5, 17, 37, 49} is stable. □

We next consider Table 2.2 in light of Theorem 3.1. Again let X_{n,j} denote the set of cycles of Φ̂_{n} of period 2^{j}. Call X_{n,j} stabilized if it consists entirely of stable cycles.

Corollary 3.1b. Assume that all X_{n,n−j} are stabilized for 0 ≤ j ≤ k − 1, and that |X_{n,n−k}| = |X_{n+1,n+1−k}| = |X_{n+2,n+2−k}|. Then X_{m,m−k} is stabilized for m ≥ n, and |X_{m,m−k}| = |X_{n,n−k}|.

This criterion gives the stabilized region indicated in Table 2.2. For n = 20 over 90% of all elements in (Z/2^{n}Z)^{∗} are in stable cycles.

4. The ax + b Conjugacy Map

Consider now the ax + b function

(4.1)  T_{a,b}(x) = \{ \begin{matrix}(ax + b)/2 & if x ≡ 1 (mod 2) \\ x/2 & if x ≡ 0 (mod 2), \end{matrix}

where ab is odd. See [4], [5], [7], and [12] for various properties of T_{a,b} under iteration on Z.

The 2-adic shift map S is conjugate to the general ax + b function T_{a,b} by the ax + b conjugacy map Φ_{a,b} : Z_{2} → Z_{2}; i.e., Φ_{a,b} ∘ S ∘ Φ_{a,b}^{−1} = T_{a,b}. If x = ∑_{l} 2^{d_{l}}, where {d_{l}} is a finite or infinite sequence with 0 ≤ d_{1} < d_{2} < ⋯, then

(4.2)  Φ_{a,b}(x) = −b ∑_{l} a^{−l}2^{d_{l}};

see [2]. Associated to Φ_{a,b} are the permutations Φ_{a,b,n} on Z/2^{n}Z obtained by reducing Φ_{a,b} mod 2^{n}. The following result generalizes Theorem 3.1.

Theorem 4.1. For the ax + b conjugacy map Φ_{a,b}, suppose that a cycle σ_{n}(x) of Φ_{a,b,n} has |σ_{n}(x)| ≥ 4. (i) If a ≡ 1 (mod 4), and σ_{n}(x) is an inert cycle, then σ_{n+1}(x) is an inert cycle. (ii) If a ≡ 3 (mod 4), and σ_{n}(x) and σ_{n+1}(x) are both inert cycles, then σ_{n+2}(x) is an inert cycle.

This theorem follows from Corollary 5.1 in §5. The proof actually shows that in case (i) the weaker hypothesis |σ_{n}(x)| ≥ 2 suffices, when b ≡ 3 (mod 4).

There are examples of ax+b conjugacy maps Φ_{a,b} for which all cycles eventually become stable. Such Φ_{a,b} then have no odd periodic points. Using Theorem 4.1 we easily check that the 25x − 3 conjugacy map when taken mod 32 has an odd part consisting of two stable cycles of period 8.

5. The Highest Order Bit

Throughout this section, Φ = Φ_{a,b} is a general ax + b conjugacy map, where a and b are odd. We analyze the high bit of the iterates of Φ mod 2^{n+2}. All earlier results follow from Theorem 5.1 below.

For x ∈ Z_{2}, expand x as

(5.1)  x = ∑_{k=0}^{∞} bit_{k}(x)2^{k},

where bit_{k}(x) is either 0 or 1. Define the bit sums

(5.2)  pop_{k}(x) := ∑_{j=0}^{k} bit_{j}(x).

The ax + b conjugacy map is then given by

(5.3)  Φ_{a,b}(x) = ∑_{k=0}^{∞} \frac{−b}{a^{pop_{k}(x)}} bit_{k}(x)2^{k},

by (4.2).

Lemma 5.1. If y, z ∈ Z_{2} with z ≡ y (mod 2^{n}), then

(5.4)

Φ(z) − Φ(y) − (z − y)

≡ 2^{n+1} (\frac{ab + 1}{2} + \frac{b(a − 1)}{2} pop_{n−1}(y)) (bit_{n}(y) + bit_{n}(z)) (mod 2^{n+2}).

Proof. Expand Φ(z) − Φ(y) (mod 2^{n+2}) using (5.3). We have bit_{k}(z) = bit_{k}(y) and pop_{k}(z) = pop_{k}(y) for 0 ≤ k ≤ n − 1, so the first n terms in Φ(z) − Φ(y) cancel. Thus

Φ(z) − Φ(y) ≡ 2^{n} ((\frac{−b}{a^{pop_{n}(z)}} ) bit_{n}(z) − (\frac{−b}{a^{pop_{n}(y)}} ) bit_{n}(y))

+ 2^{n+1} ((\frac{−b}{a^{pop_{n+1}(z)}} ) bit_{n+1}(z) − (\frac{−b}{a^{pop_{n+1}(y)}} ) bit_{n+1}(y)) .

Substitute a^{−1} ≡ a (mod 4) in the coefficient of 2^{n}, and b ≡ a^{−1} ≡ 1 (mod 2) in the coefficient of 2^{n+1}:

(5.5)

Φ(z) − Φ(y) ≡ 2^{n}(ba^{pop_{n}(y)} bit_{n}(y) − ba^{pop_{n}(z)} bit_{n}(z))
+ 2^{n+1}(bit_{n+1}(z) − bit_{n+1}(y)) (mod 2^{n+2}).

On the other hand

(5.6) z − y ≡ 2^{n}(bit_{n}(z) − bit_{n}(y)) + 2^{n+1}(bit_{n+1}(z) − bit_{n+1}(y)) (mod 2^{n+2}).

Subtract (5.6) from (5.5):

Φ(z)−Φ(y)−(z−y) ≡ 2^{n}((ba^{pop_{n}(y)}+1) bit_{n}(y)−(ba^{pop_{n}(z)}+1) bit_{n}(z)) (mod 2^{n+2}).

Substitute a^{k} ≡ 1 + (a − 1)k (mod 4), pop_{k}(x) bit_{k}(x) = (1 + pop_{k−1}(x)) bit_{k}(x), and then pop_{n−1}(z) = pop_{n−1}(y):

Φ(z) − Φ(y) − (z − y)

≡ 2^{n}((b(1 + (a − 1) pop_{n}(y)) + 1) bit_{n}(y)

− (b(1 + (a − 1) pop_{n}(z)) + 1) bit_{n}(z))

≡ 2^{n}((ab + 1 + b(a − 1) pop_{n−1}(y)) bit_{n}(y)

− (ab + 1 + b(a − 1) pop_{n−1}(z)) bit_{n}(z))

≡ 2^{n}((ab + 1 + b(a − 1) pop_{n−1}(y))(bit_{n}(y) − bit_{n}(z))

≡ 2^{n+1} (\frac{ab + 1}{2} + \frac{b(a − 1)}{2} pop_{n−1}(y)) (bit_{n}(y) − bit_{n}(z)) (mod 2^{n+2}).

This is equivalent to (5.4). □

Now fix x ∈ Z_{2}, and fix n ≥ 0. Set |σ_{n}(x)| = 2^{j} and assume from now on that

(5.7)  σ_{n+1}(x) is inert,

so that |σ_{n+1}(x)| = 2^{j+1}. We wish to determine whether or not σ_{n+2}(x) is inert. According to (3.2) this occurs if and only if

(5.8)  Φ^{2^{j+1}}(x) ≡ x + 2^{n+1} (mod 2^{n+2}).

We now introduce the quantities

e_{k}[i] := bit_{k}(Φ^{i}(x)).

In terms of the e_{k}[i], we have

(5.9)  σ_{n+2}(x) is inert ⟺ e_{n+1}[0] ≠ e_{n+1}[2^{j+1}],

by (5.8). We proceed to evaluate e_{n+1}[2^{j+1}] − e_{n+1}[0] mod 2. The main theorems of this paper are deduced from the following formula.

Theorem 5.1. If |σ_{n}(x)| = 2^{j} and σ_{n+1}(x) is an inert cycle, then

(5.10)  e_{n+1}[2^{j+1}] − e_{n+1}[0] ≡ 1 + \frac{ab + 1}{2}2^{j} + \frac{b(a − 1)}{2}N (mod 2),

where

(5.11)  N = ∑_{i=0}^{2^{j}−1} pop_{n−1}(Φ^{i}(x)).

Proof. First we define X_{i} = (Φ^{i+1+2^{j}}(x) − Φ^{i+1}(x)) − (Φ^{i+2^{j}}(x) − Φ^{i}(x)). Since σ_{n+1}(x) is an inert cycle, Φ^{i+2^{j}}(x) ≡ Φ^{i}(x) + 2^{n} (mod 2^{n+1}), so, by Lemma 5.1,

X_{i} ≡ 2^{n+1} (\frac{ab + 1}{2} + \frac{b(a − 1)}{2} pop_{n−1}(Φ^{i}(x))) (mod 2^{n+2}).

Adding up the X_{i} gives

(5.12)  ∑_{i=0}^{2^{j}−1} X_{i} ≡ 2^{n+1} (\frac{ab + 1}{2}2^{j} + \frac{b(a − 1)}{2}N) (mod 2^{n+2}).

Next define Y_{i} = 2^{n}((e_{n}[i + 1 + 2^{j}] − e_{n}[i + 1]) − (e_{n}[i + 2^{j}] − e_{n}[i])). The sum of the Y_{i} telescopes:

∑_{i=0}^{2^{j}−1} Y_{i} = 2^{n}(e_{n}[2^{j+1}] − e_{n}[2^{j}] − e_{n}[2^{j}] + e_{n}[0]).

Since σ_{n+1}(x) is an inert cycle, e_{n}[0] = e_{n}[2^{j+1}] ≠ e_{n}[2^{j}], so

(5.13)  ∑_{i=0}^{2^{j}−1} Y_{i} = 2^{n}(2e_{n}[0] − 2e_{n}[2^{j}]) ≡ 2^{n+1} (mod 2^{n+2}).

On the other hand,

\begin{aligned}X_{i} − Y_{i} & ≡ 2^{n+1}(e_{n+1}[i + 1 + 2^{j}] − e_{n+1}[i + 1] − e_{n+1}[i + 2^{j}] + e_{n+1}[i]) \\ & ≡ 2^{n+1}(e_{n+1}[i + 1 + 2^{j}] + e_{n+1}[i + 1] − e_{n+1}[i + 2^{j}] − e_{n+1}[i]). \end{aligned}

In this form the sum of X_{i} − Y_{i} also telescopes:

∑_{i=0}^{2^{j}−1}(X_{i} − Y_{i}) ≡ 2^{n+1}(e_{n+1}[2^{j+1}] − e_{n+1}[0]) (mod 2^{n+2}).

Comparing this sum with (5.12) and (5.13), we get

2^{n+1}(e_{n+1}[2^{j+1}] − e_{n+1}[0]) ≡ 2^{n+1} (\frac{ab + 1}{2}2^{j} + \frac{b(a − 1)}{2}N) − 2^{n+1} (mod 2^{n+2}),

which implies (5.10). □

Corollary 5.1. (i) If a ≡ 1 (mod 4), then

e_{n+1}[2^{j+1}] − e_{n+1}[0] ≡ \{ \begin{matrix}1 (mod 2) if b ≡ 3 (mod 4) or j ≥ 1 \\ 0 (mod 2) otherwise. \end{matrix}

(ii) If a ≡ 3 (mod 4), and σ_{n}(x) is inert, then

e_{n+1}[2^{j+1}] − e_{n+1}[0] ≡ \{ \begin{matrix}1 (mod 2) if j ≥ 2, \\ 0 (mod 2) if j = 1. \end{matrix}

Note that (i) proves Theorem 4.1(i), and (ii) proves Theorem 4.1(ii), using (5.9). Theorem 3.1 then follows as a special case of Theorem 4.1(ii).

Proof. (i) Here a ≡ 1 (mod 4), so the term involving N in (5.10) drops out.

(ii) Here a ≡ 3 (mod 4), and j ≥ 1, so (5.10) simplifies to

e_{n+1}[2^{j+1}] − e_{n+1}[0] ≡ 1 + N (mod 2).

The inertness of σ_{n}(x) gives

bit_{n−1}(Φ^{i+2^{j−1}}(x)) = 1 − bit_{n−1}(Φ^{i}(x)),

so

pop_{n−1}(Φ^{i+2^{j−1}}(x)) + pop_{n−1}(Φ^{i}(x)) ≡ 1 (mod 2).

Thus

N = ∑_{i=0}^{2^{j−1}−1} (pop_{n−1}(Φ^{i+2^{j−1}}(x)) + pop_{n−1}(Φ^{i}(x))) ≡ ∑_{i=0}^{2^{j−1}−1} 1 = 2^{j−1} (mod 2).

Now (ii) follows. □

6. Cycle Structure of Φ̂_{n}: Short Cycles

We consider the behavior of “short” cycles of the 3x + 1 conjugacy map; i.e., the behavior of |X_{n,j}| as n → ∞ for fixed j. We describe a heuristic model which relates the asymptotics of |X_{n,j}| to the number of global odd periodic points of Φ.

We first note that the odd periodic points Per^{∗}(Φ) of Φ determine the entire set Per(Φ) of periodic points of Φ. The relation

(6.1)  Φ(2x) = 2Φ(x)

implies that x has period 2^{j} if and only if 2x has period 2^{j}. Thus

(6.2)  Per(Φ) = {2^{k}x : k ≥ 0 and x ∈ Per^{∗}(Φ)} .

Let F_{j} be the number of orbits of Φ containing an odd periodic point of minimal period 2^{j}. The 3x + 1 Conjugacy Finiteness Conjecture of §2 asserts that all F_{j} are finite.

We obtain a simple heuristic model for the 1-cycles X_{n,1} of Φ̂_{n} by classifying them into two types: those arising by reduction mod 2^{n} from an odd fixed point of Φ, and all the rest. Call these “immortal” and “mortal” 1-cycles, respectively. Our heuristic model is to assume that each “mortal” 1-cycle has equal probability of splitting or remaining inert, independently of all other 1-cycles. When a “mortal” 1-cycle splits, both its progeny in X_{n+1,1} are “mortal.” An “immortal” 1-cycle in X_{n,1} always splits, and gives rise to two 1-cycles in X_{n+1,1}, at least one of which is “immortal.” We also assume that only F_{0} “immortal” 1-cycles appear in total, i.e., for all large enough n each “immortal” 1-cycle splits into one “immortal” 1-cycle and one “mortal” 1-cycle.

This model is a branching process model with two types of individuals. The expected number of individuals Z_{n,1} at step n is

(6.3)  E[Z_{n,1}] = F_{0}n + c_{0},

where c_{0} is a constant depending on the levels of the initial occurrences of the F_{0} “immortal” 1-cycles. The empirical data in Tables 6.3 and 6.4 seem consistent with this model, with F_{0} = 2. We know that F_{0} ≥ 2 in any case. The two “immortal” 1-cycles that we know of both appear at n = 1, so that if F_{0} = 2, then c_{0} = 0 in (6.3).

To obtain a heuristic model for |X_{n,j}| when j ≥ 1, we use a refined classification of cycles of Φ̂_{n}. A step consists of passing from Φ̂_{n−1} to Φ̂_{n}. For 0 ≤ d ≤ j ≤ n let X_{n,j,d} denote the set of cycles of Φ̂_{n} of size 2^{j} which have remained inert for exactly d steps. Let Y_{n,j,d} denote the subset of X_{n,j,d} that consists of cycles that split in going to Φ̂_{n+1}. Then we have

|X_{n+1,j,0}| = 2 ∑_{d=0}^{n} |Y_{n,j,d}|

and

|X_{n+1,j+1,d+1}| = |X_{n,j,d}| − |Y_{n,j,d}| .

We know the following facts about these quantities:

(1) If a cycle of length at least 8 has been inert for d ≥ 2 steps, it remains inert. Thus |Y_{n,j,d}| = 0 if j ≥ 3 and d ≥ 2.

(2) Any cycle of length 4 which has been inert for d = 2 steps must split; i.e., |X_{n,2,2}| = |Y_{n,2,2}|.

(3) Any odd periodic point x of Φ of period 2^{j} gives rise to a cycle of period 2^{j} of Φ̂_{n} for all sufficiently large n. This cycle always splits. Such cycles are in both X_{n,j,0} and Y_{n,j,0}.

The quantity we are interested in is

|X_{n,j}| = ∑_{d=0}^{n} |X_{n,j,d}| .

The facts above imply that |X_{n,j}| is entirely determined by knowledge of |X_{m,j,0}|, |Y_{m,j,0}|, and |Y_{m,j,1}|, for all m ≤ n.

Our heuristic model is then to suppose the following:

(1) Each cycle in X_{n,j,1} has (independently) probability 1/2 of falling in Y_{n,j,1}.

(2) Each “mortal” cycle in X_{n,j,0} has (independently) probability 1/2 of falling in Y_{n,j,0}, and if so its two progeny in X_{n+1,j,0} are “mortal.”

(3) Each “immortal” cycle in X_{n,j,0} lies in Y_{n,j,0}, and one of its progeny in X_{n+1,j,0} is “immortal” and the other is “mortal,” with finitely many exceptions.

This is a multi-type branching process model. If Z_{n,j} denotes the total number of individuals in such a process, then one may calculate that, for large n,

(6.4)  E[Z_{n,1}] = \frac{1}{4}F_{0}n^{2} + (F_{1} + \frac{1}{4}F_{0})n − F_{1} + \frac{1}{2}F_{0} + c_{1},

in which c_{1} is a constant depending on the initial occurrence of “immortal” cycles. (We assume that c_{0} = 0.) For j ≥ 2, where stable cycles may occur, the formula for E[Z_{n,j}] becomes quite complicated.

It might be interesting to further compare predictions of this model for j ≥ 1 with actual data for Φ. We know of one odd periodic cycle of Φ of length 2, namely {1, −1/3}; i.e., Φ(1) = −1/3 and Φ(−1/3) = 1. Thus F_{1} ≥ 1.

Appendix A. Solenoidal Maps

Call a map F : Z_{2} → Z_{2} solenoidal if, for all n,

(A.1)  x ≡ y (mod 2^{n}) ⟹ F (x) ≡ F (y) (mod 2^{n}).

An equivalent condition in terms of the 2-adic metric |·|_{2} is that F is nonexpanding; i.e.,

(A.2)  |F (x) − F (y)|_{2} ≤ |x − y|_{2} ,  all x, y ∈ Z_{2}.

If F_{1} and F_{2} are solenoidal maps, then so is F_{1} ∘ F_{2}.

Call a family of functions F_{n} : Z/2^{n}Z → Z/2^{n}Z compatible if F_{n} agrees with F_{n−1} under projection π_{n} : Z/2^{n}Z → Z/2^{n−1}Z; i.e., if π_{n} ∘ F_{n} = F_{n−1} ∘ π_{n}. A compatible family {F_{n}} has an inverse limit F : Z_{2} → Z_{2} defined by

(A.3)  F (x) ≡ F_{n}(x) (mod 2^{n}),  for all n.

The term “solenoidal” is justified by the following lemma.

Lemma A.1. F is solenoidal if and only if F is the inverse limit of a compatible family {F_{n}}.

Proof. If F is solenoidal, then F mod 2^{n} induces a function F_{n} : Z/2^{n}Z → Z/2^{n}Z, for each n; and {F_{n}} is a compatible family. The reverse implication follows from (A.3). □

Lemma A.2. Let U be the inverse limit of a compatible family {U_{n}}. Then the following are equivalent. (i) U is a bijection. (ii) For each n, U_{n} is a permutation. (iii) For each n, if U(x) ≡ U(y) (mod 2^{n}) then x ≡ y (mod 2^{n}).

Proof. (i) ⟹ (ii). U is surjective, so U_{n} is surjective.

(ii) ⟹ (i). Write V_{n} = U_{n}^{−1}. Then {V_{n}} is a compatible family. Let V be its inverse limit. By construction U ∘ V is the inverse limit of identity functions, so U ∘ V is the identity. Similarly V ∘ U is the identity. Hence U is a bijection.

(ii) ⟹ (iii). If U(x) ≡ U(y) (mod 2^{n}) then U_{n}(x mod 2^{n}) = U_{n}(y mod 2^{n}) so x mod 2^{n} = y mod 2^{n}.

(iii) ⟹ (ii). Suppose that U_{n}(a) = U_{n}(b). Select x and y in Z_{2} such that a = x mod 2^{n}, b = y mod 2^{n}. Then U_{n}(x mod 2^{n}) = U_{n}(y mod 2^{n}), so U(x) ≡ U(y) (mod 2^{n}), so x ≡ y (mod 2^{n}), so a = b. □

Corollary A.3. The following are equivalent. (i) U is a solenoidal bijection. (ii) U is a solenoidal homeomorphism. (iii) U is a 2-adic isometry.

U is a 2-adic isometry if |U(x) − U(y)|_{2} = |x − y|_{2}.

Proof. (i) ⟹ (iii). U is solenoidal so |U(x) − U(y)|_{2} ≤ |x − y|_{2}. On the other hand, by Lemma A.1, U is an inverse limit; and U is a bijection, so |U(x) − U(y)|_{2} ≥ |x − y|_{2} by Lemma A.2(i ⟹ iii).

(iii) ⟹ (ii). Since |U(x) − U(y)|_{2} ≤ |x − y|_{2}, U is solenoidal. By Lemma A.1, U is an inverse limit; by Lemma A.2(iii ⟹ i), U is a bijection. Since |U(x) − U(y)|_{2} ≥ |x − y|_{2}, U^{−1} is solenoidal. Finally, solenoidal implies continuous.

(ii) ⟹ (i). Immediate. □

Appendix B. Functions Solenoidally Conjugate to the Shift

For any two solenoidal bijections V_{0}, V_{1} define U_{V_{0},V_{1}} : Z_{2} → Z_{2} by

U(x) = \{ \begin{matrix}V_{0}(x/2) & if x ≡ 0 (mod 2), \\ V_{1}((x − 1)/2) & if x ≡ 1 (mod 2). \end{matrix}

For example, take V_{0}(x) = x and V_{1}(x) = ax + (a + b)/2; then U_{V_{0},V_{1}} is the ax + b function.

In this appendix we show that a map is solenoidally conjugate to the 2-adic shift map S—i.e., conjugate to S by a solenoidal bijection—if and only if it is of the form U_{V_{0},V_{1}}.

Lemma B.1. Let V be a solenoidal bijection. If z ≡ w (mod 2^{m−1}) then V (z) ≡ V (w) + z − w (mod 2^{m}).

Proof. If z ≡ w (mod 2^{m}) then V (z) ≡ V (w) (mod 2^{m}).

If z ≡ w + 2^{m−1} (mod 2^{m}) then still V (z) ≡ V (w) (mod 2^{m−1}). By Corollary A.3, V is an isometry, so if V (z) ≡ V (w) (mod 2^{m}) then z ≡ w (mod 2^{m}), contradiction. Thus V (z) ≡ V (w) + 2^{m−1} (mod 2^{m}). □

Lemma B.2. Set U = U_{V_{0},V_{1}}. Fix m ≥ 1. If y ≡ x + 2^{m}e (mod 2^{m+1}) then U(y) ≡ U(x) + 2^{m−1}e (mod 2^{m}).

Proof. Put b = x mod 2; then U(x) = V_{b}(S(x)). Also U(y) = V_{b}(S(y)), since y ≡ x (mod 2). We have S(y) ≡ S(x) + 2^{m−1}e (mod 2^{m}); by Lemma B.1, V_{b}(S(y)) ≡ V_{b}(S(x)) + 2^{m−1}e (mod 2^{m}). □

Lemma B.3. Set U = U_{V_{0},V_{1}}. Fix m ≥ j ≥ 1. If y ≡ x + 2^{m}e (mod 2^{m+1}) then U^{j}(y) ≡ U^{j}(x) + 2^{m−j}e (mod 2^{m−j+1}).

Proof. Lemma B.2 and induction on j. □

Lemma B.4. Set U = U_{V_{0},V_{1}}. Fix m ≥ 1. If y ≡ x + 2^{m}e (mod 2^{m+1}) then U^{m}(y) ≡ U^{m}(x) + e (mod 2).

Proof. Lemma B.3 with j = m. □

Lemma B.5. Set U = U_{V_{0},V_{1}}. Fix b_{0}, b_{1}, b_{2}, … ∈ {0, 1}. Define x_{0} = 0 and x_{m+1} = x_{m} + 2^{m}(b_{m} − U^{m}(x_{m})). Then y ≡ x_{m} (mod 2^{m}) if and only if U^{i}(y) ≡ b_{i} (mod 2) for 0 ≤ i < m.

Proof. We induct on m. For m = 0 there is nothing to prove.

Say y ≡ x_{m+1} (mod 2^{m+1}). Then y ≡ x_{m} + 2^{m}(b_{m} − U^{m}(x_{m})) (mod 2^{m+1}); by Lemma B.4, U^{m}(y) ≡ U^{m}(x_{m}) + b_{m} − U^{m}(x_{m}) = b_{m} (mod 2). Also y ≡ x_{m} (mod 2^{m}), so by the inductive hypothesis U^{i}(y) ≡ b_{i} (mod 2) for 0 ≤ i < m.

Conversely, say U^{i}(y) ≡ b_{i} (mod 2) for 0 ≤ i ≤ m. By the inductive hypothesis y ≡ x_{m} (mod 2^{m}). Write y = x_{m} + 2^{m}e. Then b_{m} ≡ U^{m}(y) ≡ U^{m}(x_{m}) + e (mod 2) by Lemma B.4. Thus y ≡ x_{m} + 2^{m}(b_{m} − U^{m}(x_{m})) = x_{m+1} (mod 2^{m+1}). □

Theorem B.1. Set U = U_{V_{0},V_{1}}. Define Q(x) = ∑_{m=0}^{∞}(U^{m}(x) mod 2)2^{m}. Then Q is a solenoidal bijection, and U = Q^{−1} ∘ S ∘ Q.

Thus any map of the form U_{V_{0},V_{1}} is solenoidally conjugate to S. (See Theorem B.2 below for the converse.) Q^{−1} generalizes the ax + b conjugacy map.

Proof. Injective: Say Q(y) = Q(x). Define b_{m} = U^{m}(x) mod 2; then U^{m}(y) ≡ U^{m}(x) ≡ b_{m} (mod 2). Next define x_{0} = 0 and x_{m+1} = x_{m} + 2^{m}(b_{m} − U^{m}(x_{m})). By Lemma B.5, y ≡ x_{m} (mod 2^{m}) and x ≡ x_{m} (mod 2^{m}). Thus y ≡ x (mod 2^{m}) for every m; i.e., y = x.

Solenoidal: Say y ≡ x (mod 2^{n}). Define b_{m} = U^{m}(x) mod 2, x_{0} = 0, and x_{m+1} = x_{m} + 2^{m}(b_{m} − U^{m}(x_{m})). Then x ≡ x_{n} (mod 2^{n}) by Lemma B.5, so y ≡ x_{n} (mod 2^{n}); by Lemma B.5 again, U^{m}(y) ≡ b_{m} (mod 2) for 0 ≤ m < n. Thus Q(y) ≡ Q(x) (mod 2^{n}).

Surjective: Given b = ∑_{i=0}^{∞} b_{i}2^{i} with b_{i} ∈ {0, 1}, define x_{0} = 0 and x_{m+1} = x_{m}+ 2^{m}(b_{m} − U^{m}(x_{m})). Since x_{m+1} ≡ x_{m} (mod 2^{m}) the sequence x_{1}, x_{2}, … converges to a 2-adic limit y, with y ≡ x_{m} (mod 2^{m}). By Lemma B.5, U^{m}(y) ≡ b_{m} (mod 2) for all m. Thus Q(y) = b.

Finally, it is immediate from the definition of Q that Q ∘ U = S ∘ Q. □

Theorem B.2. Let Q be a solenoidal bijection. Define U = Q^{−1} ∘ S ∘ Q. Then U = U_{V_{0},V_{1}} for some solenoidal bijections V_{0}, V_{1}.

Proof. If Q(0) is even then Q^{−1}(x) ≡ x (mod 2) for all x; so write

Q^{−1}(x) = \{ \begin{matrix}2W_{0}(x/2) & if x ≡ 0 (mod 2), \\ 1 + 2W_{1}((x − 1)/2) & if x ≡ 1 (mod 2). \end{matrix}

Then W_{0}, W_{1} are solenoidal bijections, and U = U_{V_{0},V_{1}} where V_{i} = Q ∘ W_{i}. Similarly, if Q(0) is odd then Q^{−1}(x) ≡ −1 − x (mod 2) for all x; so write

Q^{−1}(x) = \{ \begin{matrix}1 + 2W_{0}(x/2) & if x ≡ 0 (mod 2), \\ 2W_{1}((x − 1)/2) & if x ≡ 1 (mod 2). \end{matrix}

Again W_{0}, W_{1} are solenoidal bijections, and U = U_{V_{0},V_{1}} where V_{i} = Q ∘ W_{i}. □

References

1. E. Akin, Why is the 3x + 1 problem so hard?, to appear, Math. Magazine.

2. D. J. Bernstein, A non-iterative 2-adic statement of the 3x + 1 conjecture, Proc. Amer. Math. Soc. 121 (1994), 405–408.

3. M. Boyle, J. Franks, B. Kitchens, Automorphisms of one-sided subshifts of finite type, Ergod. Th. Dyn. Sys. 10 (1990), 421–449.

4. R. E. Crandall, On the ‘3x + 1’ problem, Math. Comp. 32 (1978), 1281–1292.

5. Z. Franco, C. Pomerance, On a conjecture of Crandall concerning the QX + 1 problem, to appear, Math. Comp. 49 (1995).

6. G. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375.

7. E. Heppner, Eine Bemerkung zum Hasse-Syracuse Algorithmus, Arch. Math. 31 (1978), 317– 320.

8. J. C. Lagarias, The 3x + 1 problem and its generalizations, Amer. Math. Monthly 92 (1985), 3–23.

9. J. C. Lagarias, The set of rational cycles for the 3x + 1 problem, Acta Arithmetica 56 (1990), 33–53.

10. H. Müller, Das ‘3n + 1’ Problem, Mitteilungen der Math. Ges. Hamburg 12 (1991), 231–251.

11. H. Müller, Über eine Klasse 2-adischer Funktionen im Zussamenhang mit dem “3x + 1”- Problem, Abh. Math. Sem. Univ. Hamburg 64 (1994), 293–302.

12. R. P. Steiner, On the “QX + 1 problem,” Q odd, I, II, Fibonacci Quart. 19 (1981), 285–288, 293–296.

Department of Mathematics, University of California, Berkeley, CA 94720 Current address: Department of Mathematics, Statistics, and Computer Science, The Univer-

sity of Illinois at Chicago, Chicago, IL 60607–7045 16 DANIEL J. BERNSTEIN, JEFFREY C. LAGARIAS

E-mail address: djb@math.uic.edu

AT&T Bell Laboratories, Murray Hill, NJ 07974

E-mail address: jcl@research.att.com