The 3x+1
problem and Number Representation
Ranan B. Banerji
Professor Emeritus
7,
rbanerji@sju.edu
David Hecker
Department of Mathematics and Computer Science
Abstract
The 
function C (also known as the Collatz function)
is defined as follows on positive integers:
if
x is odd and 
otherwise.
It is conjectured that repeated applications of C to any positive integer always ends in the loop 1-4-2-1. No counterexample is known, but no proof is known either. Our purpose has been to study as many properties of this function as we can. These specific properties may or may not lead to a proof for the original conjecture. It is our belief that the more properties of this function that are known, the greater the number of tools available for the proof.
First, we introduce the restriction g of the Collatz function on odd positive integers. We then construct a representation for positive odd integers based upon a mixture of binary and ternary representations for numbers. In many cases, this mixed representation makes computation of g much easier. Using this number representation, we study certain vertical segments of the tree representing the function g, discovering useful internal properties of these segments, as well as investigating how each segment propagates others like it in the tree.
1. Introduction. In
two previous papers [1], [2] we have studied some properties of the following
modification of the function [4] defined
on positive odd integers x:
,
where l is the integer which
reduces the right-hand side to an odd integer. This function is the
function 
defined by Belaga and Mignotte [3], and
essentially retains all the properties of the Collatz function as restricted on
odd integers (the effect of the Collatz function on even itegers being
trivial). We will graphically illustrate
the actions of this function using a tree structure similar to the Collatz tree
[4], but with additional structure added in accordance with the following
theorem regarding the function g.
(For the rest of this paper integer will mean positive integer)
Theorem 1.1: For all
integers n
and odd integers x:
(a) 
(Note that 
) for some integer k.)
(b) 
if
n is odd.
(c) 
.
(d) If 
then there does not
exist a positive odd integer y such that
.
(e) If 
or 
, then there is a unique positive odd integer 
such that 
and 
for any k.
In particular, 
(n must be even), and 
(n must be odd).
Proof of Theorem 1.1:
(a) 
.
(b) If n is even then 
is odd, as is 
. Using the computation in (a), above, we see that 
, yielding the desired conclusion.
(c) 
which
is odd. Moreover 
for any k.
(d) Suppose 
. Then 
for some integer l. But 
does not contain a 3 in
its prime factorization, so neither does x.
(e) First
we prove the existence part of (e). Suppose 
. Here n must be even, so (b) above
applies. Also 
for any k.
Hence, 
is a preimage of 
under g that does not equal 
. Also if 
then n is odd so 
(where
). From (c) above the required result follows, noting that 
.
For the
uniqueness part of (e), let 
be the least odd
integer y such that
. For all 
, define 
, and let z be an
odd integer such that 
. We claim that there
is a j such that 
and that, for all , 
, for some 
, thus establishing uniqueness.
To prove the
claim, first note that 
. Also, the sequence 
is increasing and
approaches infinity, and so there is a unique j such that 
. Thus, 
. Now if 
, then we also have 
. In addition, suppose 
. Now, 
contradicts the inequality 
. Similarly 
contradicts the inequality 
. If
, then 
, implying 
. But the right side
of this is divisible by 3 and the left side is not. Hence, the only case possible is 
, which implies 
.
For all , 
is odd, and so is of
the form 
. The
claim that for 
follows easily from
this. ¢
It will be noted that Theorem 1.1
(a),(b),(c) define g(x)
for all odd integers. Also Theorem 1.1 (e) defines h(x) for odd integers for which h(x)
is defined. We now draw a small part of the tree structure for g (see Figure 1) illustrating the
properties from Theorem 1.1. Moving
downward in the tree corresponds to applying g. Moving horizontally from
left to right corresponds to applying the function 
. Moving directly
upwards (not at a slant) corresponds to applying h.
Figure
1: A small portion of the tree for the
function g
Figure 1 illustrates several additional patterns. First, traversing horizontally to the right,
the numbers increase by 1 mod 3. This
can be easily proven in general. All but
the first number in each horizontal line equal for some k.
Second, all straight vertical paths (except for the trivial loop path
containing 1) seem to terminate eventually going upwards (this is at present an
unproven conjecture), with the terminal
number equaling 0 mod 3 as indicated in Theorem 1.1 (d). All straight vertical paths (except for the
trivial loop path) seem to terminate eventually going downwards (presently a
second unproven conjecture) at a number
of the form 8k+5, since according to Theorem 1.1 (a) the path goes in a slant
at this point. We will investigate the properties of these vertical paths
later.
2. Number
Representation. Next, we prepare to
introduce a method of representing positive odd integers which helps illuminate
the properties of the vertical paths in the tree for g. To help define this
representation, we first note that every positive odd integer x can be expressed as 
, where represents the number
of consecutive 1’s in the base 2 representation of x, going from right to left.
If we define the function 
, we then have
Theorem 2.1: If 
, then 
.
The proof of Theorem 2.1 is an
easy, straightforward computation. The
significance of the theorem is that, if we use the correct notation, 
becomes easy to
compute for many values of x. In particular, we introduce the following
notation for an odd positive integer x. If , then we express x
as 
. Furthermore, if m is the string representing y in base 3, we write x as 
. We will refer to the
form as the mixed representation of x. Theorem 2.1 can now be rewritten as
Corollary 2.2: If , then 
.
For example, 
. Now
, and 
, and so 
.
It is
clear, for , that 
. Thus,
Corollary 2.3: If
with
, then 
.
The mixed
representation is also useful in computing many values of the inverse function . In particular, we
have
Theorem 2.4:
If and 
, then 
.
This theorem says that h inverts the process in Corollary 2.2.
Proof of Theorem 2.4: By Corollary 2.2, 
. Hence, to prove the
theorem, we must show that 
does not have the form , or else we have chosen the wrong preimage of 
under g.
But every positive integer of the form has mixed
representation of the form 
, since has a 0 in the 2’s
place in base 2. However, 
, and so does not have the form
. ¢
Theorem 2.4
shows that it is useful to know when x
has the form ; that is, the form with 
. The following lemma
tells us this, and more.
Lemma 2.5: Suppose 
and . (Hence
.) Then,
(a) 
(b) 
(c) 
It is useful to note that 
when i is odd, and 
when i is even. Lemma 2.5 is then easily
proven by computing 
in a straightforward
manner for each of the five cases in the lemma listed on the right.
3. Strips. The number representations defined in Section 2 make it clear that the tree representing the function g will contain many vertical segments of the form illustrated in Figure 2. Moving downward on the tree corresponds to applying g, while moving upward corresponds to applying h.
Figure 2: A vertical segment of the tree for the function g
Corollary 2.3 implies that the
number values increase as we move down the segment. Also, none of the numbers, except for
possibly the last, can be of the form , since an “” has mixed representation . Finally, in the case
in which the last number, z, is not of the form , the segment can be continued downward by computing 
. Then
, since 
. Also, this 
. The last congruence
follows from Theorem 1.1 (b), since 
and z is of the form , so that w must be
even.
Lemma 2.5 further implies that all
but possibly the first number in this segment must be congruent to 2 mod 3. The first number y is congruent to 2 modulo 3 only if 
, for some p. In this case, Theorem 2.4 indicates that h(y) is defined and equals
. Since p can end in at most a finite number of
1’s, repeated application of h will
eventually produce a number of the form 
for which the ending
digit of q is not a 1. By Lemma 2.5, this number will be equivalent to
either 0 mod 3 or to 1 mod 3.
We put together the above observations to define a specific type of segment in the tree for g, which we call a strip.
Definition: A strip in the tree for g is a vertical segment of length 
such that:
(a) The top (starting) number in the segment is congruent to either 0 or 1 mod 3. This number will sometimes referred to as the beginning of the strip.
(b) The
bottom (ending) number in the segment is congruent to 1 mod 3 or equals (or both). We shall
occasionally refer to this number as the end of the strip.
(c) Traversing upward corresponds to applying h
(d) All
numbers strictly between the starting and ending numbers are congruent to 
Property (c) of a strip implies
traversing downward in a strip corresponds to applying g. It also implies that only
the ending number can be of the form .
Let us consider an example of a vertical segment of the tree for g and illustrate how it divides into strips. (See Figure 3.) To conserve space, Figure 3 displays the segment horizontally, with “moving right” corresponding to “moving down.” The figure gives the numbers as well as their mixed representations and their equivalence mod 3.
Figure 3: Four strips in the tree for g
The four strips in Figure 3 illustrate most of the different
types of strips. The first strip has
starting number congruent to 0 mod 3, while the remaining strips start with 1
mod 3. Notice that consecutive strips
share a number congruent to 1 mod 3.
Thus, a number x congruent to
1 mod 3 and not equal to is a member of two
different strips – at the end of one strip (x’s
secondary strip) and at the beginning
of the next (x’s primary strip). The strip 121 – 91 in Figure 3 shows that a strip
can have just two elements, with no “
” terms in the middle.
The last strip displayed ends with a number of the form
, which can not
begin a new strip, since it is not the image of any number under h.
Applying g to an “” jumps far down the tree diagonally, not vertically, in
accordance with Theorem 1.1(a).
One final
type of strip not illustrated in Figure 3 is one which ends with an “” that is congruent to 2 mod 3. An example of this type strip would be
15 - 23 - 35 - 53 = 8(6)+5 = 3(17)+2.
Numbers 
and equal do not appear in any
strip. This is because for such an x, 
does not exist by
Theorem 1.1(d), and x is not the
image of any number under h because
it is of the form . Hence, a vertical segment containing x of length 
can not be
formed. All other positive odd integers
appear in some strip. Also, the number
“1” appears in the unusual strip 1 –
1. We call those numbers, other than 1,
that appear in some strip, ordinary.
It will be
noticed that the mixed representation of the end of a strip bears very little
relation to that of the number just above it. The reason is that this last number is the
result of applying g to a number of
the form 
. The resulting number
is of the form 
, i.e. can be written as the ternary number w1, as if the pattern in Fig. 2 is being
continued with 
; however, the mixed representation of this number is related
to this ternary representation in no obvious way. In a later section, we shall occasionally
refer to this number as “w1*” or “y&0” by an abuse of notation.
4. Beginnings and Ends of Strips. Next, we develop conditions that tell us how a strip begins and how it ends, just by examining properties of a single number in the strip.
Theorem 4.1: Let be ordinary. Let j
be the number of 1’s at the end of the string m. Then the beginning of the
(primary)[1]
strip containing x is congruent to 
if and only if either
(a) the
rightmost digit of m unequal to 1 is
0, and 
is even, or
(b) the rightmost digit of m
unequal to 1 is 2, and is odd.
Proof of Theorem
4.1: The integer z at the beginning of a strip must equal
0 or 1 mod 3, and, by Lemma 2.5(b) and (c), must have either a 0 or a 2 to the immediate left of the * in
its mixed representation. Going down the strip by repeatedly applying g (using Corollary 2.2), we see that the
sum of the number of 1’s directly to the left of the * plus the number to the
right of the * remains unchanged. Thus, 
, where i and j are as in the Theorem. But Lemma 2.5(c) shows the precise conditions
under which 
, completing the proof. ¢
Next, we
study the possible endings of strips.
First of all, in a (primary)
strip containing , x must be followed by at
least 
more numbers in the
strip, since the next numbers in the strip
are computed using Corollary 2.2. We
will see later that in a strip containing , x will be
followed by at most i more numbers; that is, the strip must
end either at x (which happens when 
and m is odd), or at most i numbers after x. Moreover, the ending
number z for a strip must fall into
one of three categories:
Type (a): 
and ,
Type (b): and 
,
Type (c): 
and .
If z is of Type
(a), then it not only ends this one strip, but it also begins the next
strip. Three of the four strips in
Figure 3 end like this. If z is of Type (b), then this strip ends
the entire vertical path of which it is a part at one of the horizontal lines
in the tree. Applying g from here descends diagonally. The last strip in Figure 3 ends like
this. Also, the strip 75 – 113 – 85 in
Figure 1 has a Type (b) ending. If z is of Type (c), then the strip ends
abruptly without an ending “1 mod 3.” It
also ends its entire vertical path. The
strips 15 – 23 – 35 – 53 and 151 – 227 – 341 in Figure 1 have Type (c)
endings. It is impossible for a strip to
end in a “
,” because such numbers are not ordinary. They do not appear
in any strips.
First we will determine necessary and sufficient conditions that a strip has a Type (c) ending. We will need the following lemma:
Lemma 4.2: Suppose 
, with . Then, applying g changes the parity of both y and i.
Proof of Lemma 4.2: Since applying g subtracts 1 from i, the
parity of i clearly changes. Also, Theorem 2.1 shows that g changes y to 
, which has the opposite parity of y. ¢
Definition: A number with is short-ending if and only if y and i have the same parity.
As we shall see in the next theorem, numbers of the form 
that are short-ending
reside in strips ending 
steps after with ending numbers of
Type (c). For example, all of the
numbers in the strips
15 - 23 - 35 - 53 and 151 – 227 – 341
we discussed above are short-ending, since the & number representation for the numbers in these strips are
0&4 - 1&3 - 4&2 - 13&1 and 9&3 – 28&2 – 85&1.
Also, because such strips end with an “,” they end the longer vertical path of which they are a
part. Note how each strip ends
exactly steps after each
number in the strip.
Theorem 4.3: Let with i ³ 1 . Let 
. Then
if and only if x is short-ending. Furthermore, if , 
.
Note in Theorem 4.3 that since , if 
, then z ends the
(primary) strip containing x.
Proof of Theorem 4.3:
By Corollary 2.2 and Lemma 4.2, 
, where w has the
same parity as y if i is odd, and has the opposite parity as
y if i is even. But 
equals if and only if w is odd. If i
is odd, y and w have the same parity, and so if and only if y is also odd. Similarly, if i is even, w and y have opposite
parity, and so if and only if y is also even. Hence, x
is short-ending if and only if .
Finally, if , 
, because Corollary 2.2 has been applied at least once. Hence, by Lemma 2.5(a).
¢
Note that every “” is of the form 
with y odd, and thus y and 1 have the same parity.
However, this number does not have to be congruent to 2 mod 3. If a number x is an “” but is congruent to 1 mod 3, then x ends a strip, but does not begin a new one. Hence, x does not have a primary strip, and the
parenthetical comment in Theorem 4.3 does not apply.
Next, we determine which numbers lie in strips ending with a number of Type (b). These strips end the longer vertical path in which they lie.
Definition: A number 
for is long-ending if and only if one of the
following is true:
(i) 
and 
(ii)
and 
(iii)
and 
(iv)
and 
It is easy to see that the conditions on a number being long-ending are mutually exclusive from those for a number to be short-ending, since each y and corresponding i in the definition of long-ending have opposite parity.
Now, the number 175 = 12*4 = 5&4 in Figure 3 is long-ending (part (iv) of the definition). Its strip, shown in Figure 3, ends with a number of Type (b). The numbers 263 = 16&3, 395 = 49&2 and 593 = 148&1 in that same strip are also long-ending.
Theorem 4.4: Suppose be ordinary, with . If x is long-ending, then 
ends the (primary) strip containing x, with and .
Proof of Theorem 4.4: Suppose x
is long-ending. If with
, then we claim that is also
long-ending. Corollary 2.2 says that g decreases i by 1 (mod 4), and y
becomes , which changes as follows:
if 
, 
; if 
, 
; if 
, 
; if 
, 
. Hence, the values of
y mod 8 follow the cycle 0,1,4,5,0,1… properly with the values of i mod 4. This argument and
Corollary 2.2 assures us that 
, with 
, and that u is in
the strip containing x. In addition, since Corollary 2.2 has been
applied at least once, 
, and so 
by Lemma 2.5. For the case 
, we let 
. Then
as well.
Now 
. Thus, 
, and so is not of the form . Now, if 
, u is not the end
of its strip. Otherwise, if u is 0 or
1 mod 3, u has just started its primary strip, and so is not at the end
of the strip. In any of these cases, 
. But
, producing both forms required by the theorem. ¢
A qualified converse to Theorem 4.4
can be proved. The problem is that
Theorem 4.3 takes precedence over such a converse. It is possible for both 
and 
to be congruent to 5
mod 8, in which case the strip containing x
stops short at and does not continue
on to . In this case x is short-ending, and is not long-ending. The number 
in Figure 4
illustrates this, as both 
and 
are congruent to 5 mod 8. Note that 3223 is not
long-ending, but is short-ending instead.
Figure 4: Conflict between Theorem 4.3 and the converse of Theorem 4.4
The example in Figure 4 was
discovered as follows: we found the first “
” on the lowest horizontal line on the tree. This is 85.
Next, we computed 
. Finally, we moved
horizontally from 113 until we encountered the first “
.” This is 7253. The numbers in the strip ending at 7253 are
short-ending, since 7253 is a “.” However, 7253 was
constructed to have its image under g
to be a “.” Many such examples
can be constructed by starting at any “,” applying h, and
then moving horizontally to a “.”
Theorem 4.5: Suppose with such that x is not short-ending. Let . Then if and , then x is
long-ending.
Proof of Theorem 4.5: First we consider the case . Because x is not short-ending,
, for some n, and
so 
. Hence, 
. But
. Therefore, 
, or 
, implying n is
even. If 
, then 
, or 
, implying j is
odd. Therefore, 
, for j odd, or 
. Thus, x is long-ending.
Now suppose . Let
, with 
, in accordance with Corollary 2.2. By Lemma 2.5(a), 
, and by Lemma 4.2, 
is not short-ending,
since x is not short-ending. Thus, by the contrapositive of Theorem 4.3, 
, and so p does not
end the strip containing x. Hence, by the case, p is long-ending. Now the proof of Theorem
4.4 established that applying 
cycles the congruences
of numbers, mod 8, through the correct sequence to maintain the long-ending
property as we progress down a strip.
However, f is a one-to-one
correspondence on the residues mod 8, and so its inverse also cycles these
congruences correctly to maintain the long-ending property as we progress back
up the strip from p to x using the formula in Theorem 2.4. Therefore, since p is long-ending, x must
also be long-ending. ¢
Our next theorem describes the only remaining case for the ending of a strip.
Theorem 4.6: Suppose 
, and is neither short- nor long-ending. Then the (primary) strip containing x ends exactly i steps after x with a
Type (a) ending.
Proof of Theorem 4.6: First consider the case . Since x is not
short-ending, then y is even. Hence
. Thus, x is
ordinary and does not end the strip.
Furthermore, 
, and so the (primary)
strip stops after exactly one step. Also, 
, or else x would be long-ending, by Theorem
4.5. Therefore the strip ends with a
Type (a) ending.
Now suppose . We know that the
strip must contain at least numbers after x, with 
. Since
, 
, and so by Lemma 2.5(a). Also, since x is not short- or long-ending, neither is
p.
Hence , by the contrapositive of Theorem 4.3. Therefore p
is not the end of the strip. Also, p satisfies the conditions of the
theorem for . And so, by the case, the proof of the
theorem is complete. ¢
5. Strip Generation. Consider the section of the tree for g given in Figure 5, and note
the relationship between the &
representations of the two strips beginning with 7 and 15. The numbers 15 – 23 – 35 have very similar
representations to the numbers 7 – 11 – 17; the numbers before the & in 7,11 and 17 are the same as those before the & in 15,23
and 35 respectively and the numbers after the & 15,23and 35 are one higher
than those in the corresponding numbers in the first strip. While this pattern does not continue on to
the ends of the strips, we will occasionally, “informally,” refer to a number
such as 13 by “13&0” so that the observed pattern does continue. Not only does
this notation continue the pattern, but it is also in agreement with the image 
predicted by Part (b)
of Theorem 1.1.
The
relationship between the first three numbers in the two strips is that the
function 
maps the numbers in
the first strip to the numbers in the second strip. But, this is to be expected as the mapping sends 
to 
, as we have observed.
The ending numbers in the strip are related by the function
, as always along the horizontal lines of the tree.
The
relationship between strips we have observed in Figure 5 occurs between every
pair of strips in the tree that occur at consecutive “” and “
” positions contiguous along a horizontal line. We will say that the first strip generates the second strip. We will define other instances of strip generation
below. But first, we prove in general the informal observations we have already
made. The next two lemmas will help.
Lemma 5.1: Let 
. Then 
, and
(i)
if , then 
,
(ii)
if , then 
, and
(iii)
if 
, then 
.
The proof of Lemma 5.1 is easy.
Lemma 5.2: If 
is not of the form then
(a)
If 
then 
(b)
If 
then 
Proof of Lemma 5.2: Suppose 
. Then by Lemma 5.1, 
. If
, then 
with y even, and so 
“
.” But, by Corollary
2.2, 
, which equals 
, as claimed in part (b).
If , then 
, by Corollary 2.2.
Also, 
, as claimed in part (a). ¢
In what
follows, we will use an italic letter X
to denote the strip 
of length n, beginning at 
and ending at 
.
Theorem 5.3: If X is a strip of length n ending with 
, and 
, for 
, and 
, then 
is a strip of length n ending with 
. Furthermore, 
implies
, and 
implies 
.
The strip X in Theorem 5.3 is said to generate the strip Y. The strips 
and 
shown in Figure 5
provide an example of Theorem 5.3.
However, notice that while the strip X
in Figure 5 ends with 
, Theorem 5.3 does not
require that . Theorem 5.3 applies to any strip ending with
. Hence, Theorem 5.3
states that a strip with either Type (a) or Type (b) ending always generates a
strip with a Type (c) ending.
Proof of Theorem 5.3: Consider Theorems 4.3, 4.4 – 4.5, and 4.6
using the number 
. Because the end of the strip containing x is 
, we must be in the case of either Theorem 4.4 – 4.5, or 4.6;
that is, the strip is not short-ending.
Hence, 
, with w and 
having opposite
parity, and 
for 
. By Lemma 5.1 
, where w and n have the same parity, and 
for . Thus, the strip
containing 
is short-ending,
stopping at 
, by Theorem 4.3 (note that 
). Corollary 2.2 and
Theorem 4.3 clearly indicate that the sequence 
is a segment of a
strip. We must still show that begins the strip and
that 
ends the strip; that
is, 
.
First,
since X is a strip, 
0 or 1 mod 3. Hence,
by Lemma 5.1, if
then , and if then . In either case, starts a strip. And
finally, the fact that 
follows directly from
Lemma 5.2(b). ¢
Next, we
consider what kind of strip is generated by a strip ending with
.
Lemma 5.4: Let x be an odd positive integer. Then,
(a) 
(b) If
, then
Proof of Lemma 5.4:
Now 
. Since half of this
is odd, 
, proving part (a).
For part
(b), if 
, then 
= 
= 
= 
. On the other hand, 
, and so
= 
. Now 
= 
. On division by 4,
this equals 
, completing the proof. ¢
Theorem 5.5: If X is a strip of length n ending with , and , for 
, 
, and 
, then 
is a strip of length 
ending with 
. Furthermore, implies
, and implies .
Again, we say that the strip X in Theorem 5.5 generates the strip Y. Figure 6 gives two examples of this type of strip generation. Note that the strip X and the generated strip Y are typically not near each other on the tree for g. Also note that
while both strips Y1 and Y2 end with a number 
, Y2
ends with an “,” while Y1
does not. Hence, strips with a Type (c)
ending can generate either a strip with a Type (a) ending or one with a Type
(b) ending.
Proof of Theorem 5.5:
Again, consider Theorems 4.3, 4.4 – 4.5, and 4.6 using the number
. Because the end of the strip containing x is 
, we must be in the case of Theorem 4.3; that is, the strip X is short-ending. Hence, 
, with w and 
having the same
parity, and 
for 
. By Lemma 5.1, 
, where w and 
have opposite parity,
and 
for . Thus, the strip
containing is not short-ending,
stopping at 
, by Theorems 4.4 through 4.6. Corollary 2.2 and Theorems 4.4 through 4.6
clearly indicate that the sequence 
is a segment of a
strip. Since the strip stops at 
, we know that it has two more numbers in it beyond . Lemma 5.4 shows that
these two numbers must be and 
. Theorems 4.4 and 4.6
also show that 
.
We must still show that begins the strip Y.
But, since X
is a strip, 0 or 1 mod 3.
Hence, by Lemma 5.1, if then
, and if then . This shows that starts a strip, and
proves the last line of the theorem. ¢
6. Seeds: We will see that every strip of length 
is generated by a
unique strip. However, some strips of
length 2 and 3 are not generated by any strip.
But, we can show that certain single numbers, which we call seeds, serve as the generators of these
strips.
Definition: A seed is a nonnegative integer x of one of the following forms:
(i)
(ii)
Note that a Type (ii) seed is even. Also, if and only if 
. Theorems 6.1 and 6.2
describe the strips generated by each of these seeds.
Theorem 6.1: Let be a seed, and let 
, 
, and 
. Then 
is a strip (the strip generated by x). Furthermore, 
.
For
example, the seed 21 (
) generates the strip (43, 65, 49), and the seed 85 (
) generates the strip (171, 257, 193).
Theorem 6.2: Let 
be a seed (and so x is not congruent to ), and let and 
. Then 
is a strip (the strip generated by x). Furthermore, 
.
The even
seed 12 (
) generates the strip (25, 19).
Proof of Theorem 6.1: , Since 
0 or 1 mod 3, by Lemma 5.1, 
or 0 mod 3. Also, implies
. This shows that can start a
strip. Lemma 5.4 yields 
and 
. The forms of the
formulae for 
and 
clearly imply that 
and that
. Finally, 
. Hence
, satisfies all criteria to be a strip. ¢
Proof of Theorem 6.2: Again, since 0 or 1 mod 3, by Lemma 5.1, or 0 mod 3. Also, implies
. This shows that can start a
strip. Then 
. Dividing by 4 yields
= 
= 
= 
. The form 
for shows that . Hence , satisfies all criteria to be a strip. ¢
We can now show that every strip is generated by a unique strip or seed.
Theorem 6.3: For every strip Y there is a unique strip X or a unique seed x that generates Y (but not both).
Proof of Theorem 6.3:
Let be a strip. Then 
is odd, and so there
is a unique x such that
. We need to show that either x is a seed generating the strip Y, or that x starts a
strip X which generates the strip Y.
Doing this will complete the proof.
In the case 
, Y must be the
strip (3, 5), which is generated by the strip (1,1). So, we will now assume that 
.
First, by
Lemma 5.1, since must be congruent to
either 0 or 1 mod 3, x must be
congruent to either 1 or 0 mod 3.
Now, if , then x is a seed,
and Y must be the strip generated by x in accordance with Theorem 6.1, since can only start one
strip.
Next, if x is even, then we claim that 
, and is a seed. If
not, then 
, and so 
, which means that can not start a strip
– a contradiction. Thus, is a seed, and must
generate the strip Y in accordance
with Theorem 6.2.
Finally,
suppose that x is odd and that 
. Then x is the
starting number for some strip X. Theorems 5.3 and 5.5 describe how X generates the strip beginning with . Hence X generates
Y, as required. ¢
7. The Strip Sequence Generated by a Seed. Finally, we will study
properties of the sequence of strips generated by a single seed. Let 
represent the mth strip generated by the
seed s. That is, s generates 
, and 
generates . Usually, we will just write 
instead of when the seed s being discussed is clear from
context. The theorems from sections 5
and 6 reveal several patterns. Our first two theorems completely describe how
the strip begins.
Theorem 7.1: Let 
be a seed. Then 
, the first number in , equals 
. Furthermore,
if 
then 
for m odd, and 
for m even. Similarly,
if 
then for m odd, and for m even.
Theorem 7.2: Let 
be a seed. Then , the first number in , equals 
. Furthermore,
if 
then for m odd, and for m even. Similarly,
if 
then for m odd, and for m even.
Proof of Theorem 7.1: We proceed by induction on m. For the base step, Theorem 6.2
implies that 
. From this, Lemma 2.5 shows that 
has the correct value
mod 3. For the inductive step, assume that satisfies the theorem
and prove the theorem for 
. But from Theorems 5.3 and 5.5, we know that
. Lemma 5.1 completes the proof. ¢
Proof of Theorem 7.2:
We proceed by induction on m. For the
base step, Theorem 6.1 implies that 
. Also, Lemma 5.1 and 
shows that has the correct value
mod 3. For the inductive step, assume
that satisfies the theorem
and prove the theorem for . But from Theorems 5.3 and 5.5, we know that
. Lemma 5.1 completes
the proof. ¢
The next theorems describe the ending types of the strips generated by a seed.
Theorem 7.3: Let s be a seed. Then, if m is even, ends with a type (c)
ending. If m is odd, ends with either a
type (a) or a type (b) ending.
Proof of Theorem 7.3: From both Theorems 7.1 and 7.2 we see that if 
, then y and i have opposite parities. Hence, is not short-ending.
However, increasing m by 1 increments
i by 1, but does not change y. Hence, 
will be short-ending, 
will not, etc. Applying Theorem 4.3 completes the
proof.█
Because
when m is even, is short-ending, then
entire strip is computed using
Corollary 2.2. Hence, we can easily give an explicit formula for the ending
number of , just by using the starting numbers from Theorems 7.1 and
7.2 and applying Corollary 2.2 repeatedly.
Theorem 7.4: Let s be a seed, and let m be even. Then,
(i)
If , then has length m and 
.
(ii)
If , then has length 
and 
.
Furthermore, the ending number of is congruent to 5 mod 8 and is congruent to 2 mod 3.
Proof of Theorem 7.4: Theorem 7.4 was essentially proved just
before the statement of the theorem. The formula for 
in part (i) is found
by starting with 
, converting 
to a number w in base 3, and applying Corollary 2.2 
times, producing 
. The formula given in
part (i) is this value written as a regular decimal
integer. The formula in part (ii) is
computed similarly. The last statement
of the theorem is just restating what it means for a strip to have a type (c)
ending. ¢
Now we show which strips have type (a) endings, and which have type (b) endings.
Theorem 7.5: Let be a seed, and let m be odd. Then has length
, 
, and
(i)
If n is odd,
then has a type (a) ending,
(ii)
If 
and 
, then has a type (a) ending,
(iii)
If and 
, then has a type (b) ending,
(iv)
If 
and , then has a type (b) ending,
(v)
If and , then has a type (a) ending.
Proof of Theorem 7.5: If 
, Theorem 6.2 gives an exact formula for the entire strip , which has length 
and has 
, agreeing with the formula for 
in this theorem.
Now suppose 
. Then Theorem 7.4
gives shows that 
has length
, and gives a precise formula for its ending number. Now apply Theorem 5.5 to to obtain
. Theorem 5.5 shows
that must have length 
, and gives a formula for computing the ending number of from that of . Using these formulas
and simplifying gives the result for 
stated in the theorem.
To prove parts (i) through (v), we
will check whether or not is long-ending. If it
is, then has a type (b) ending,
by Theorem 4.4. If it is not, since we have
already established in the proof of Theorem 7.3 that is not short-ending,
the contrapositive of Theorem 4.5 will show that has a type (a) ending.
First note that, from Theorem 7.1, . Now, if n is odd,
or 
. Hence is not long-ending,
establishing part (i). For parts (ii)
and (iii), implies
. Thus, is long-ending only when . Finally, for parts
(iv) and (v), implies
. Thus, is long-ending only when . ¢
Finally, we consider the endings of the odd numbered strips in the sequence of strips generated by an odd seed.
Theorem 7.6: Let be a seed, and let m be odd. Then has length
, 
, and
(i)
If k is odd,
then has a type (a) ending,
(ii)
If 
and , then has a type (b) ending,
(iii)
If and , then has a type (a) ending,
(iv)
If 
and , then has a type (a) ending,
(v)
If and , then has a type (b) ending.
The proof of Theorem 7.6 parallels that of Theorem 7.5.
Proof of Theorem 7.6: If , Theorem 6.1 gives an exact formula for the entire strip , which has length 
and has 
, which simplifies to 
, as does the formula for 
in this theorem.
Now suppose . Then Theorem 7.4
gives shows that has length m, and gives a precise formula for its
ending number. Now apply Theorem 5.5 to to obtain
. Theorem 5.5 shows
that must have length , and gives a formula for computing the ending number of from that of . Using these formulas
and simplifying gives the result for 
stated in the theorem.
To prove parts (i) through (v), we
will check whether or not is long-ending. If it is,
then has a type (b) ending,
by Theorem 4.4. Otherwise, Theorem 4.5
will show that has a type (a) ending.
First note that, from Theorem 7.2, 
. Now, if k is odd,
or 
. Hence is not long-ending,
establishing part (i). For parts (ii)
and (iii), implies
. Thus, is long-ending only when