Working with 2s and 3s
Working with 2s and 3s
Diego Dominici ∗
Department of Mathematics
State University of New York at New Paltz
1 Hawk Dr.
New Paltz, NY 12561-2443
Phone: (845) 257-2607
Fax: (845) 257-3571
October 22, 2018
Abstract
We establish an equivalent condition to the validity of the Collatz
conjecture, using elementary methods. We derive some conclusions
and show several examples of our results. We also offer a variety of
exercises, problems and conjectures.
1 Introduction
The Collatz conjecture (also known as the 3n + 1 conjecture, Ulam’s con-
jecture, the Syracuse problem, Kakutani’s problem, Hasse’s algorithm, etc.)
was first proposed by Lothar Collatz in 1937 [2]. In terms of the function
T (n), defined by
T (n) =
, n ≡ 1(mod 2)
, n ≡ 0(mod 2)
, n ∈ N, (1)
∗e-mail: dominicd@newpaltz.edu
http://arxiv.org/abs/0704.1057v1
the conjecture claims that for all natural numbers n, there exists a natural
number k such that
T (k) (n) = T ◦ T ◦ · · · ◦ T
︸ ︷︷ ︸
k times
(n) = 1.
For example, we have
T (3) = 5, T (2)(3) = 8, T (3)(3) = 4, T (4)(3) = 2, T (5)(3) = 1,
T (7) = 11, T (2)(7) = 17, T (3)(7) = 26, T (4)(7) = 13, T (5)(7) = 20, (2)
T (6)(7) = 10, T (7)(7) = 5, T (8)(7) = 8, T (9)(7) = 4, T (10)(7) = 2, T (11)(7) = 1.
We define T (∞) (n) = 1.
Exercise 1 Prove that if ∀n ∈ N ∃ k ∈ N such that T (k) (n) < n, then the
Collatz conjecture is true. The number k is called the stopping time of n.
As of February 2007, the Collatz conjecture has been verified for numbers
up to 13×258 = 3, 746 , 994, 889, 972, 252, 672 [7]. However, the general case
remains open.
Introducing the total stopping time function σ∞(n), defined by σ∞(1) = 0
σ∞(n) = inf
k ∈ N ∪ {∞} | T (k) (n) = 1
, n ≥ 2,
we can reformulate the Collatz conjecture as
C = N, (C1)
where
C = {n ∈ N | σ∞(n) < ∞} . (3)
From (2), we have
n 2 3 4 5 6 7 8
σ∞(n) 1 5 2 4 6 11 3
Exercise 2 Find σ∞(n) for 9 ≤ n ≤ 100.
Hint: The web page http://www.numbertheory.org/php/collatz.html con-
tains an implementation which allows the computation of σ∞(n) for large
values of n.
http://www.numbertheory.org/php/collatz.html
One could consider the inverse problem and try to characterize the sets
Sk, defined by S0 = {1} and
Sk = {n ∈ N | σ∞(n) = k} , k ≥ 1. (4)
The first few Sk are
S1 = {2} , S2 = {4} , S3 = {8} , S4 = {5, 16} , S5 = {3, 10, 32} , (5)
S6 = {6, 20, 21, 64} , S7 = {12, 13, 40, 42, 128} , S8 = {24, 26, 80, 84, 85, 256} .
It is clear from (4) that 2k ∈ Sk ∀k ∈ N0, where N0 = N ∪ {0} . In terms of
the sets Sk, the Collatz conjecture reads
Sk = N. (C2)
Exercise 3 Compute Sk for 9 ≤ k ≤ 100.
Hint: Consider the inverse map T−1 : N → P (N) , given by
T−1(n) =
{2n} , n ≡ 0, 1(mod 3)
2n, 1
(2n− 1)
, n ≡ 2(mod 3)
The sequence of natural numbers
n , n ≥ 0
, defined by x
0 = m
n+1 = T
x(m)n
, 0 ≤ n, (6)
is called the trajectory or forward orbit of m ∈ N. From (2), we have
= {2, 1} ,
= {3, 5, 8, 4, 2, 1} ,
= {4, 2, 1} ,
x(5)n
= {5, 8, 4, 2, 1} ,
x(6)n
= {6, 3, 5, 8, 4, 2, 1} ,
x(7)n
= {7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1} ,
x(8)n
= {8, 4, 2, 1} .
Exercise 4 Find
for 9 ≤ m ≤ 100.
Using the sequences
we can restate Collatz’s conjecture as
x(m)n
= {2, 1} . (C3)
We can also consider higher order recurrences, i.e., instead of (6), use
n+i = T
, 0 ≤ n,
where
T (i) (x) = fi,j(x), if x ≡ j
mod 2i
, 0 ≤ j ≤ 2i − 1. (7)
For i = 1, 2, 3, we have
f1,0(x) =
, f1,1(x) =
3x+ 1
f2,0(x) =
, f2,1(x) =
3x+ 1
, f2,2(x) =
3x+ 2
, f2,3(x) =
9x+ 5
f3,0(x) =
, f3,1(x) =
9x+ 7
, f3,2(x) =
3x+ 2
, f3,3(x) =
9x+ 5
f3,4(x) =
3x+ 4
, f3,5(x) =
3x+ 1
, f3,6(x) =
9x+ 10
, f3,7(x) =
27x+ 19
Exercise 5 Prove that if the sequence {3k + 4 } ⊂ C, then the Collatz con-
jecture is true.
In terms of (7), the Collatz conjecture reads
∀n ∈ N ∃ m ∈ N such that n ≡ k (mod 2m) and
fm,k(x) < 1. (C4)
For example, we have 11 ≡ 11 (mod 25) and
f5,10(x) =
3x+ 2
, f5,11(x) =
27x+ 23
Thus,
5 = f5,11(11) = 10, x
10 = f5,10(10) = 1.
The literature on the Collatz conjecture is vast and growing rapidly.
Rather than attempting to cover it, we refer the reader to the excellent
survey papers [5] and [6].
2 Representation of natural numbers
Let the sets Λm be defined by Λm = {2
m} , 0 ≤ m ≤ 3 and
n ∈ N | n =
, m ≥ 4,
for some m, l, b1, . . . , bl ∈ N0, with
0 ≤ l ≤ m− 3 and 0 ≤ b1 < b2 < · · · < bl ≤ m− 4.
The first few Λm are
Using the (l + 2)−tuple (l, b1, . . . , bl, m) to represent the number
we can write
Λ4 = {(0, 4) , (1, 0, 4)} , Λ5 = {(0, 5) , (1, 1, 5) , (2, 0, 1, 5)} ,
Λ6 = {(0, 6) , (1, 0, 6) , (1, 2, 6) , (2, 1, 2, 6)} , (8)
Λ7 = {(0, 7) , (1, 1, 7) , (1, 3, 7) , (2, 0, 3, 7), (2, 2, 3, 7)} ,
Λ8 = {(0, 8) , (1, 0, 8) , (1, 2, 8) , (1, 4, 8) , (2, 1, 4, 8), (2, 3, 4, 8)} .
Exercise 6 Compute Λm for 9 ≤ m ≤ 100.
Hint: (a) If (v1, v2, . . . , vl+2) ∈ Λm, then (v1, v2 + 1, . . . , vl+2 + 1) ∈ Λm+1.
(b) (1, 0, 2m) ∈ Λ2m for all m ≥ 2.
Comparing (5) with (8), it seems that Sm = Λm. The next results will
show this to be true.
Lemma 7 For all m ∈ N0, we have
T (Λm+1) ⊂ Λm. (9)
Proof. Let n ∈ Λm+1. Then,
T (n) =
2bk−1
if b1 > 0 (n even) or
T (n) =
2bk+1
2bk+1−1
if b1 = 0 (n odd). In either case, T (n) ∈ Λm.
Lemma 8 For all m ∈ N0, we have
Λm ⊂ Sm. (10)
Proof. We use induction on m. The case of m = 0 is clearly true, since
Λ0 = {1} = S0.
Assuming (10) to be true for m, let n ∈ Λm+1. From (9) we have T (n) ∈
Λm and therefore σ∞ [T (n)] = m. Thus, σ∞(n) = m+1 and the result follows.
Exercise 9 Show that
T (n) =
. (11)
The other inclusion is also true.
Theorem 10 For all m ∈ N0,
Sm ⊂ Λm.
Proof. Clearly, Sm = {2
m} = Λm, 0 ≤ m ≤ 3.
Let m ≥ 4 and s ∈ Sm. Using (11) we can write the recurrence (6) as
n+1 =
x(s)n +
0 = s, (12)
where
θn = sin
x(s)n
, i.e., x(s)n ≡ θ
n (mod 2) . (13)
Assuming {θn} to be a known sequence, the solution of (12) is [1]
x(s)n = 2
j + 1
j + 1
or using (13)
n = 2
−n3Θ(n−1)
3Θ(k)
, (14)
Θ (x) =
j . (15)
Setting n = m and solving for s in (14), we obtain
m = 1
3Θ(m−1)
3Θ(k)
. (16)
Let l = Θ (m− 1) . From (13) and (15), we see that Θ (x) is a step function
with unit jumps at x = b1, b2, . . . , bl, m, where 0 ≤ b1 < b2 < · · · < bl < m.
Therefore, we can rewrite (16) as
Finally, since x
m−3 = 8, x
m−2 = 4, x
m−1 = 2 and x
m = 1, the penul-
timate jump must occur before or at x = m − 4. Thus, bl ≤ m − 4 and
l = Θ (m− 1) ≤ m− 3.
Corollary 11 The Collatz conjecture is true if and only if every natural
number n can be represented in the form
for some m, l, b1, . . . , bl ∈ N0, with
0 ≤ l ≤ m− 3 and 0 ≤ b1 < b2 < · · · < bl ≤ m− 4.
Corollary 11 is not a proof of the Collatz conjecture, but it provides a lot
of information on the set C and the function σ∞(n). When l = 0, we recover
the known fact that 2m ∈ Sm, ∀m ∈ N0. For l = 1, we have the following
result.
Lemma 12 For all m ∈ N, we have
∈ Sm, 0 ≤ k ≤
, m even,
22k+1
∈ Sm, 0 ≤ k ≤
, m odd.
Proof. Let n ∈ Λm, with l = 1. We have
2m − 2b1
= 2b1 ×
2m−b1 − 1
, 0 ≤ b ≤ m− 4.
Thus, 2m−b1 ≡ 1 (mod 2) and therefore m− b1 ≡ 0 (mod 2) . Considering the
cases m even and m odd, the result follows.
When l = 2, the situation is slightly more complicated. To simplify
matters, we restrict ourselves to the case of n being odd.
Proposition 13 For all m ≥ 5, with m 6= 6, 8, we have
2m−2−6k
∈ Sm, 1 ≤ k ≤
, m ≥ 10 even,
2m−4−6k
∈ Sm, 0 ≤ k ≤
, m ≥ 5 odd.
Proof. Let n ∈ Λm, odd, with l = 2. Then,
2m − 3− 2b2
and therefore
2m − 2b2 = 2b2 ×
2m−b2 − 1
≡ 3 (mod 9) .
Considering all possible cases, we have
1) 2b2 ≡ 1 (mod 9) and 2m−b2 − 1 ≡ 3 (mod 9), which implies
b2 ≡ 0 (mod 6) , m− b2 ≡ 2 (mod 6) .
2) 2b2 ≡ 2 (mod 9) and 2m−b2 − 1 ≡ 6 (mod 9), which implies
b2 ≡ 1 (mod 6) , m− b2 ≡ 4 (mod 6) .
3) 2b2 ≡ 4 (mod 9) and 2m−b2 − 1 ≡ 3 (mod 9), which implies
b2 ≡ 2 (mod 6) , m− b2 ≡ 2 (mod 6) .
4) 2b2 ≡ 5 (mod 9) and 2m−b2 − 1 ≡ 6 (mod 9), which implies
b2 ≡ 5 (mod 6) , m− b2 ≡ 4 (mod 6) .
5) 2b2 ≡ 7 (mod 9) and 2m−b2 − 1 ≡ 3 (mod 9), which implies
b2 ≡ 4 (mod 6) , m− b2 ≡ 2 (mod 6) .
6) 2b2 ≡ 8 (mod 9) and 2m−b2 − 1 ≡ 6 (mod 9), which implies
b2 ≡ 3 (mod 6) , m− b2 ≡ 4 (mod 6) .
Thus, for m even we shall have m − b2 ≡ 2 (mod 6) or b2 ≡ m − 2 (mod 6)
and for m odd we need m − b2 ≡ 4 (mod 6) or b2 ≡ m − 4 (mod 6) , with
1 ≤ b2 ≤ m− 4. Writing b2 in terms of m, the result follows.
From Corollary 11, we can also get an idea of how the total stopping time
σ∞(n) behaves if the Collatz conjecture is true. Solving for m in (C5) we
ln (2)
3ln+ 3l
In other words, σ∞(n) lies on the family of parametric curves
ln (2)
3in+ j
, i, j ∈ N0, i ≤ j.
For example, we have
n 2 3 4 5 6 7 8
σ∞(n) 1 5 2 4 6 11 3
(i, j) (0, 0) (2, 5) (0, 0) (1, 1) (2, 10) (5, 347) (0, 0)
Exercise 14 Prove that
ln(n)
ln(2)
≤ σ∞(n) ∀n ∈ N.
2.0.1 Binary sequences
Another approach is to study the sequence
, k ≥ 0
, which contains a
wealth of information.
Definition 15 Let τ : C → N be defined by
τ (n) =
σ∞(n)
2k. (17)
For example, we have
n 1 2 3 4 5 6 7 8
τ(n) 1 2 35 4 17 70 2199 8
Clearly, τ (2n) = 2n, ∀n ∈ N0.
Exercise 16 Find τ(n) for 9 ≤ n ≤ 100.
Let’s study the image of Λm by τ. We have
τ (Λ0) = {1} , τ (Λ1) = {2} , τ (Λ2) = {4} , τ (Λ3) = {8} ,
τ (Λ4) = {16, 17} , τ (Λ5) = {32, 34, 35} , τ (Λ6) = {64, 65, 68, 70} , (18)
τ (Λ7) = {128, 130, 136, 137, 140} , τ (Λ8) = {256, 257, 260, 272, 274, 280} .
Exercise 17 Let
1 , . . . , λ
where Nm = #Λm denotes the number of elements in the set Λm. Prove that
∀m ∈ N0 there exist a sequence
2m > α
1 ≥ · · · ≥ α
= 0, (19)
such that
= 2m + α
From (18), we have
m 1 2 3 4 5 6 7 8
1 0 0 0 1 3 6 12 24
2 0 0 0 0 2 4 9 18
It follows from (19) that
#Λm ≤ α
1 + 1, ∀m ≥ 0.
Using (16), we can define an inverse function for τ(n).
Definition 18 Let φ : N → Q be defined by
φ(n) =
3Φ(m−1)
3Φ(k)
where β
m−1 . . . β
0 is the binary representation of n, i.e.,
= n and Φ (x) =
For example, we have
n 1 2 3 4 5 6 7 8
φ(n) 1 2 1
4 1 2
Exercise 19 Find φ(n) for 9 ≤ n ≤ 100.
It follows from Theorem 10 that
φ ◦ τ (n) = n, ∀n ∈ N,
while (19) implies that
Sm = φ
2m, . . . , 2m + α
∩ N, ∀m ≥ 0.
In terms of φ, the Collatz conjecture reads
N ⊂ φ (N) . (C6)
With (C6), we finally reach a statement equivalent to the Collatz con-
jecture, which is independent of the original formulation in terms of T (x).
Although we have not succeeded in proving (C6), we hope that studying the
function φ(n) will shed new light on the Collatz problem.
3 Further problems
In the spirit of the Monthly, we offer a series of problems to the curious
reader. Those labeled ”Exercise” are relatively easy to prove, ”Problems”
denote results strongly supported by numerical evidence and ”Conjectures”
are those that we would really wish to prove, but that may turn out to be
false.
Conjecture 20 Prove that
σ∞(n) ≤ δ(n) ln(n) ∀n ≥ 2, (20)
where δ(n) is a slowly varying function, which might be eventually constant.
Definition 21 The Abby-Normal numbers (AN numbers). Let the scaled
total stopping time γ (n) be defined by
γ (n) =
σ∞(n)
ln(n)
, n ≥ 2.
We say that ak is the k−th AN number if
γ (ak) = max {γ (n) | ak−1 ≤ n ≤ ak} , k ≥ 1
with a0 = 2. In other words, {γ (ak)} is an increasing sequence of sharp lower
bounds for the function δ(n) defined in (20).
Exercise 22 Show that
n 1 2 3 4 5 6 7
a(n) 3 7 9 27 230, 631 626, 331 837, 799
γ(n) ≃ 4.55 5.65 5.92 21.24 22.51 23.90 24.12
From the results obtained by Eric Roosendaal [8], it follows that
6, 649, 279, 8, 400, 511, 11, 200, 681, 15, 733, 191,
63, 728, 127, 3, 743, 559, 068, 799, 100, 759, 293, 214, 567,
are possible AN numbers. We have
γ(100, 759, 293, 214, 567)≃ 35.17.
Exercise 23 Find all AN numbers in the interval [1, 000, 000, 100, 759, 293, 214, 567].
Conjecture 24 Prove that there exist infinitely many AN numbers.
Problem 25 Let Vm be the m−vector
0 , . . . , x
σ∞(m)
and L : RN → RN the linear operator defined by
L ([v1, v2, . . . vN ]) = [v2, v3, . . . vN , v1] .
Let θ (m) be the angle between Vm and L (Vm) . Prove that
< cos [θ (m)] <
, ∀m ∈ N.
< cos [θ (m)] <
, ∀m ≡ 1(2).
(iii)
cos [θ (ak)] =
Hint: See [4].
Problem 26 Prove that:
(i) ∀k ≥ 6 ∃ mk ∈ Sk such that mk + 1 ∈ Sk.
(ii) ∀k ≥ 7 ∃ mk ∈ Sk such that mk + 2 ∈ Sk.
(iii) ∀l ∈ N ∃ K ∈ N such that ∀k ≥ K ∃ mk ∈ Sk such that mk + l ∈ Sk .
Hint: See [3].
Exercise 27 Prove that
#Sk+1
Exercise 28 Let
ζ (m) = # {2 ≤ k ≤ m | σ∞(k) = σ∞(k − 1)} .
Show that
ζ (m) = 0, 2 ≤ m ≤ 12, ζ (m) = 1, 13 ≤ m ≤ 14,
ζ (m) = 2, 15 ≤ m ≤ 18, ζ (m) = 3, 19 ≤ m ≤ 20.
Conjecture 29 Prove that
ζ (m)
Problem 30 Prove that
3× 2m−5
, m ≥ 0 (21)
605× 2m−13
, m ≥ 0,
where ⌊·⌋ denotes the greatest integer function.
Problem 31 Let
1 , . . . , s
, Nm = #Sm,
2m = s
1 > s
2 > · · · > s
Prove that
2m + 22k
k+2, 0 ≤ k ≤
, m ≥ 4, m ≡ 0(mod 2)
2m + 22k+1
k+2, 0 ≤ k ≤
, m ≥ 5, m ≡ 1(mod 2).
References
[1] R. P. Agarwal. Difference equations and inequalities. Marcel Dekker Inc.,
New York, 2nd ed., 2000.
[2] L. Collatz. On the origin of the (3n+1)−problem. J. Qufu Normal Univ.
(Nat. Sci.), 12(3):9–11, 1986.
[3] L. E. Garner. On heights in the Collatz 3n+ 1 problem. Discrete Math.,
55(1):57–64, 1985.
[4] D. Gluck and B. D. Taylor. A new statistic for the 3x+1 problem. Proc.
Amer. Math. Soc., 130(5):1293–1301 (electronic), 2002.
[5] J. C. Lagarias. The 3x+1 Problem: An Annotated Bibliography (1963–
2000). eprint: arxiv:NT/0309224.
[6] J. C. Lagarias. The 3x + 1 Problem: An Annotated Bibliography, II
(2001-). eprint: arxiv:math.NT/0608208.
[7] T. Oliveira e Silva. Computational verification of the 3x+ 1 conjecture.
http://www.ieeta.pt/˜tos/3x+1.html
[8] E. Roosendaal. On the 3x + 1 problem.
http://www.ericr.nl/wondrous/index.html
http://arxiv.org/abs/math/0608208
http://www.ieeta.pt/~tos/3x+1.html
http://www.ericr.nl/wondrous/index.html
	Introduction
	Representation of natural numbers
	Binary sequences
	Further problems
