PROCEEDINGS OF THE

AMERICAN MATHEMATICAL SOCIETY

Volume 82, Number 1, May 1981

ON THE COLLATZ 3n + 1 ALGORITHM

Lynn E. garner

Abstract. The number theoretic function i(n) = i n if n is even, j(/i) — 3n + 1 if n

is odd, generates for each n a Collate sequence {j*(i)}"_o. s°(") ™ "> •»*(«) ™
5(j*_'("))• It is shown that if a Collate sequence enters a cycle other than the 4, 2,
1, 4,... cycle, then the cycle must have many thousands of terms.

1. Introduction. The Collatz 3/1+1 algorithm is defined as a function s: N —*N

on the set of positive integers by
, n _ Í n/2 if n is even,
*W 13/2+1 if n is odd.
Let i0(n) = n and J*(n) = s(sk~ '(/»)) for k G N. The Collatz sequence for « is
C(») = {5*(n)}r.o.
For example, C(17) = {17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, . . . }.
The original problem of Collatz concerns the existence of cycles in Collatz
sequences. It is conjectured that every Collatz sequence ends in the cycle
4, 2, 1, 4, .... So many people have worked on this problem in the nearly fifty
years of its existence that it is almost part of mathematical folklore. Martin
Gardner reports [2] that the conjecture has been verified for all n < 60,000,000;
Riho Terras says that the conjecture has been verified for all n < 2,000,000,000.
The only published results to date [1], [3] are probabilistic in nature, and tend to
strengthen belief in the conjecture.
This paper proves that there are no other "short" cycles: if a cycle exists which
does not contain 1, then it has many thousands of terms.
2. Stopping time. Collatz's conjecture is equivalent to the conjecture that for each
n G N, n > 1, there exists k & N such that sk(n) < n. The least k e N such that
sk(n) < n is called the stopping time of n, which we will denote by a(/i).
It is not hard to verify that
o(n) = 1 if « is even,
a(n) = 3 if n = 1 (mod 4),
a(n) = 6 if n = 3 (mod 16),
o(n) = 8 if n = 11 or 23 (mod 32),
a(n) = 11 if n = 7, 15, or 59 (mod 128),
o{n) = 13 if n = 39, 79, 95, 123, 175, 199, or 219 (mod 256),
and so forth. Everett [1] proves that almost all n e N have finite stopping time, and
Terras [3] gives a probability distribution function for stopping times. Most positive

Received by the editors April 25, 1980; presented to the Society, January 6, 1980.
1980 Mathematics Subject Classification. Primary 10L10; Secondary 10A40.
© 1981 American Mathematical Society
0002-9939/81/0000-0203/$02.00
19

License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use

 20 L. E. GARNER

integers have small stopping times; the above list accounts for 237/256 « 93% of
them. However, stopping times can be arbitrarily large, for o(2" — 1) > 2n. Some
interesting cases of larger stopping times are o(27) = 96, o(703) = 132, o(35,655) =
220, a(270,271) = 311, and ct(1,027,341)= 347. In a computation of stopping times
of integers up to 1,065,000, the largest observed stopping time was 347.

3. A term formula. Let Ck(n) consist of the first k terms of the Collatz sequence
for n. Let m (which depends on n and k) be the number of odd terms in Ck(n), and
let d¡ be the number of consecutive even terms immediately following the ith odd
term. Let d0 be the number of even terms preceding the first odd term. Then the
next term in the Collatz sequence for n is
im m off! —i
**(„) »_£_„+
2k~m
¿ -t^-
,_i2*+1 ■*<•
(1)

Note that k - m = d0 + dx + • • • + dm.

4. Coefficient stopping time. By the coefficient of sk(n) is meant the coefficient of
n in (1), namely 3m/2*~m. The coefficient stopping time of n is the least k G N such
that the coefficient of sk(n) is less than 1, and is denoted by k(/i). Thus k(/j) is the
least k such that 3m <2k~m.
It is clear that if sk(n) < n, then the coefficient of sk(n) is less than 1; thus
k(/i) < o(n) for all n £ N, n > 1. We conjecture that k(/i) = a(n), and have
verified it for all n < 1,150,000.
For m = 0 or m Ë JV, letp(w) = [m log2 3]; then 2pim) < 3m < 21+p(m).Thus if
ic(n) = k, then k — m = 1 + p(m), or k = m + 1 + p(m). These, then, are the
possible coefficent stopping times.
We can also identify those n e N with a given coefficient stopping time. Clearly,
k(/i) = 1 if and only if n is even. If k = m + 1 + p(m) > 1 is a possible coefficient
stopping time, let d0 = 0 and dx, d2, . . ., dm e N be such that </, + ••• + d¡; <
/>(/) for / = 1, 2, . . . , m — 1, and </, + ••• + ¿m = p(/w) + 1. Let x and v be
integers such that 3mx + 2x+pim)y = 1. Then k(«) = A:if and only if

" = -*( 2 3m-'2',''+ ■■+4-' J (mod 21+p(m)).

We are able to prove that k(/i) = o(n) under certain bound conditions which
arise from a study of the powers of 2 and the powers of 3.
5. Powers of 2 and 3. The behavior of a Collatz sequence is clearly related to the
way in which the powers of 2 are distributed among the powers of 3. We were
surprised to find that the powers of 2 appear to be bounded away from the powers
of 3 by an amount which grows almost as rapidly as the power of 3.
To be specific, we choose M e N, and let
b{M)= max{-log3(l - 2P<J)3-J))
j KM
and
B{M) = max{-log3(2l+i'(')3-> - 1)).
j<M l J

License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use

 THE COLLATZ 3/1+1 ALGORITHM 21

Then it follows that

2/,(m) > yn-b(M)
(2)
and
2'+/>("■)- 3m > y»-*r*0 (3)

for all m < M. The values of M at which ¿>(M) and B(M) increase are given in
Table 1, with the corresponding values of b and B. (These calculations were carried
out on a Hewlett-Packard HP-19C programmable calculator.)

M b(M) B(M) M b(M) B(M) M b(M) B(M)

1 1 306 6.267 8286 6.9
2 359 6.23 8951 7.0
3 1.535 665 9.14 9616 7.1
5 2.665 971 6.31 10281 7.2
7 2.508 1636 6.35 10946 7.3
12 3.921 2301 6.39 11611 7.4
17 2.946 2966 6.44 12276 7.6
29 3.346 3631 6.49 12941 7.8
41 4.062 4296 6.53 13606 8.0
53 5.618 4961 6.59 14271 8.4
94 4.246 5626 6.65 14936 8.9
147 4.477 6291 6.71 15601 10.2
200 4.785 6956 6.77 16266 9.4
253 5.253 7621 6.8 31867 9.9

Table 1. Values at which b(M) and B(M) increase

6. The main theorem. Now we can prove that k(m) = o(n) if the number of odd
terms encountered in the Collatz sequence is not too great. The following theorem
makes the bound condition precise.

Theorem. In the notation of (I), if k(/z) = k and

m < min{M, (/i/2)3,-S(M)(l - S^^y1},

then o(n) = k(/i).

Proof. If k(/i) = k, then 3m/2*~m < 1 and

yn-i
<-:-< =— < 4(1 - 3-*">)
24H 3' 3' 3V

License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use

 22 L. E. GARNER

by (2). Thus

2 ■*
Now if sk(n) > n, then n < (3m/2k'm)n + (m/3)(l - 3-*"*), and therefore

«<4'«(l-3-é<AÍ>)^r-31'<*í>
3 3
by (3). This leads by the hypothesis to n < n, a contradiction. Hence sk(n) < n,
and er(/i) < k. But k(«) < o(n), so a(/i) = k(/j).
It is conjectured that the bound condition in the theorem is unnecessary, or is
automatically satisfied so that o(ri) = k(/i) in all cases.
7. Application to cycles. Suppose a Collatz sequence enters a cycle which does not
contain 1. Let n be the least term of the cycle; then sk(n) = n for some k E. N.
Hence k(h) < k, so that if o{h) = k(/i), then n is not the least term of the cycle after
all. Thus if stopping time and coefficient stopping time are always the same, then
the only cycle is the 4, 2, 1, . . . cycle.
The same contradiction arises if the number of odd terms in the cycle satisfies
the bound in the theorem. Thus if there is a cycle not containing 1, the number m
of odd terms in the cycle must satisfy m > min{M, (n/2)3,_B(M)(l - 3~b(M))-x},
where n is the least term of the cycle.
Using n > 60,000,000, M = 14,000, B(M) = 8.0, and b(M) = 9.14, we find
m > 13,700, and hence k > 35,400. Thus any cycle not containing 1 must have at
least 35,400 terms.
If the number 2 billion turns out to be the lower bound for n, as alleged, then
M = 41,000,B(M) = 10.2,and b(M) = 9.9 yield m > 40,700and k > 105,000.
In any event, there is only one "short" cycle, the known one.

References
1. C. J. Everett, Iteration of the number-theoretic function fl2n) — n,f(2n + 1) — 3n + 2, Advances in
Math. 25 (1977),42.
2. M. Gardner, Mathematical games, Sei. Amer. 226 (1972), 115.
3. R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241.

Department of Mathematics, Brigham Young University, Provo, Utah 84602

License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use