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