info prev up next book cdrom email home

Collatz Problem

A problem posed by L. Collatz in 1937, also called the 3x+1 Mapping, Hasse's Algorithm, Kakutani's Problem, Syracuse Algorithm, Syracuse Problem, Thwaites Conjecture, and Ulam's Problem (Lagarias 1985). Thwaites (1996) has offered a ${\mathcal L}$1000 reward for resolving the Conjecture. Let $a_0$ be an Integer. Then the Collatz problem asks if iterating

{\textstyle{1\over 2}}a_{n-1} & for $a_{n-1}$\ even\cr
3a_{n-1}+1 & for $a_{n-1}$\ odd\cr}
\end{displaymath} (1)

always returns to 1 for Positive $a_0$. This question has been tested and found to be true for all numbers $<5.6\times
10^{13}$ (Leavens and Vermeulen 1992), and more recently, $10^{15}$ (Vardi 1991, p. 129). The members of the Sequence produced by the Collatz are sometimes known as Hailstone Numbers. Because of the difficulty in solving this problem, Erdös commented that ``mathematics is not yet ready for such problems'' (Lagarias 1985). If Negative numbers are included, there are four known cycles (excluding the trivial 0 cycle): (4, 2, 1), ($-2$, $-1$), ($-5$, $-7$, $-10$), and ($-17$, $-25$, $-37$, $-55$, $-82$, $-41$, $-61$, $-91$, $-136$, $-68$, $-34$). The number of tripling steps needed to reach 1 for $n=1$, 2, ... are 0, 0, 2, 0, 1, 2, 5, 0, 6, ... (Sloane's A006667).

The Collatz problem was modified by Terras (1976, 1979), who asked if iterating

{\textstyle{1\over 2}}t_{n-1} & for $t_{n-1}$\ ...
{\textstyle{1\over 2}}(3t_{n-1}+1) & for $t_{n-1}$\ odd\cr}
\end{displaymath} (2)

always returns to 1 for initial integer value $t_0$. If Negative numbers are included, there are 4 known cycles: (1, 2), ($-1$), ($-5$, $-7$, $-10$), and ($-17$, $-25$, $-37$, $-55$, $-82$, $-41$, $-61$, $-91$, $-136$, $-68$, $-34$). It is a special case of the ``generalized Collatz problem'' with $d=2$, $m_0=1$, $m_1=3$, $r_0=0$, and $r_1=-1$. Terras (1976, 1979) also proved that the set of Integers $S_k\equiv\{n:$ $n$ has stopping time $\leq k\}$ has a limiting asymptotic density $F(k)$, such that if $N_x(k)$ is the number of $n$ such that $n\leq x$ and $\sigma(n)\leq k$, then the limit
F(k)=\lim_{x\to\infty} {N_x(k)\over x},
\end{displaymath} (3)

exists. Furthermore, $F(k)\to 1$ as $k\to\infty$, so almost all Integers have a finite stopping time. Finally, for all $k\geq 1$,
1-F(k)=\lim_{x\to\infty} {N_x(k)\over x}\leq 2^{-\eta k},
\end{displaymath} (4)

$\displaystyle \eta$ $\textstyle =$ $\displaystyle 1-H(\theta)=0.05004\ldots$ (5)
$\displaystyle H(x)$ $\textstyle =$ $\displaystyle -x\lg x-(1-x)\lg(1-x)$ (6)
$\displaystyle \theta$ $\textstyle =$ $\displaystyle {1\over\lg 3}$ (7)

(Lagarias 1985).

Conway proved that the original Collatz problem has no nontrivial cycles of length $<400$. Lagarias (1985) showed that there are no nontrivial cycles with length $<275,000$. Conway (1972) also proved that Collatz-type problems can be formally Undecidable.

A generalization of the Collatz Problem lets $d\geq 2$ be a Positive Integer and $m_0$, ..., $m_{d-1}$ be Nonzero Integers. Also let $r_i\in\Bbb{Z}$ satisfy

r_i\equiv im_i\ \left({{\rm mod\ } {d}}\right).
\end{displaymath} (8)

T(x)={m_ix-r_i\over d}
\end{displaymath} (9)

for $x\equiv i\ \left({{\rm mod\ } {d}}\right)$ defines a generalized Collatz mapping. An equivalent form is
T(x)=\left\lfloor{m_ix\over d}\right\rfloor +X_i
\end{displaymath} (10)

for $x\equiv i\ \left({{\rm mod\ } {d}}\right)$ where $X_0$, ..., $X_{d-1}$ are Integers and $\left\lfloor{r}\right\rfloor $ is the Floor Function. The problem is connected with Ergodic Theory and Markov Chains (Matthews 1995). Matthews (1995) obtained the following table for the mapping
{\textstyle{1\over 2}}x & for $x\equiv 0\ \l...
...}(3x+k) & for $x\equiv 1\ \left({{\rm mod\ } {2}}\right)$,\cr}
\end{displaymath} (11)

where $k=T_{5^k}$.

$k$ # Cycles Max. Cycle Length
0 5 27
1 10 34
2 13 118
3 17 118
4 19 118
5 21 165
6 23 433

Matthews and Watts (1984) proposed the following conjectures.

1. If $\vert m_0\cdots m_{d-1}\vert<d^d$, then all trajectories $\{T^K(n)\}$ for $n\in \Bbb{Z}$ eventually cycle.

2. If $\vert m_0\cdots m_{d-1}\vert>d^d$, then almost all trajectories $\{T^K(n)\}$ for $n\in \Bbb{Z}$ are divergent, except for an exceptional set of Integers $n$ satisfying

\char93 \{n\in S\vert -X\leq n<X\}=o(X).

3. The number of cycles is finite.

4. If the trajectory $\{T^K(n)\}$ for $n\in \Bbb{Z}$ is not eventually cyclic, then the iterates are uniformly distribution mod $d^\alpha$ for each $\alpha\geq 1$, with
$\lim_{N\to\infty} {1\over N+1}\mathop{\rm card}\{K\leq N\vert T^K(n)\equiv j\ \left({{\rm mod\ } {d^\alpha}}\right)\}$
$ =d^{-\alpha}\quad$ (12)
for $0\leq j\leq d^\alpha-1$.

Matthews believes that the map
7x+3 & for $x\equiv 0\ \left({{\rm mod\ } {3}}...
...3}}(x-2) & for $x\equiv 2\ \left({{\rm mod\ } {3}}\right)$\cr}
\end{displaymath} (13)

will either reach 0 (mod 3) or will enter one of the cycles $(-1)$ or $(-2, -4)$, and offers a $100 (Australian?) prize for a proof.

See also Hailstone Number


Applegate, D. and Lagarias, J. C. ``Density Bounds for the $3x+1$ Problem 1. Tree-Search Method.'' Math. Comput. 64, 411-426, 1995.

Applegate, D. and Lagarias, J. C. ``Density Bounds for the $3x+1$ Problem 2. Krasikov Inequalities.'' Math. Comput. 64, 427-438, 1995.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Burckel, S. ``Functional Equations Associated with Congruential Functions.'' Theor. Comp. Sci. 123, 397-406, 1994.

Conway, J. H. ``Unpredictable Iterations.'' Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972.

Crandall, R. ``On the `$3x+1$' Problem.'' Math. Comput. 32, 1281-1292, 1978.

Everett, C. ``Iteration of the Number Theoretic Function $f(2n)=n$, $f(2n+1)=f(3n+2)$.'' Adv. Math. 25, 42-45, 1977.

Guy, R. K. ``Collatz's Sequence.'' §E16 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 215-218, 1994.

Lagarias, J. C. ``The $3x+1$ Problem and Its Generalizations.'' Amer. Math. Monthly 92, 3-23, 1985.

Leavens, G. T. and Vermeulen, M. ``$3x+1$ Search Programs.'' Comput. Math. Appl. 24, 79-99, 1992.

Matthews, K. R. ``The Generalized $3x+1$ Mapping.'' Rev. Mar. 30, 1999.

Matthews, K. R. ``A Generalized $3x+1$ Conjecture.'' [$100 Reward for a Proof.]

Matthews, K. R. and Watts, A. M. ``A Generalization of Hasses's Generalization of the Syracuse Algorithm.'' Acta Arith. 43, 167-175, 1984.

Sloane, N. J. A. Sequence A006667/M0019 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Terras, R. ``A Stopping Time Problem on the Positive Integers.'' Acta Arith. 30, 241-252, 1976.

Terras, R. ``On the Existence of a Density.'' Acta Arith. 35, 101-102, 1979.

Thwaites, B. ``Two Conjectures, or How to win ${\mathcal L}$1100.'' Math.Gaz. 80, 35-36, 1996.

Vardi, I. ``The $3x+1$ Problem.'' Ch. 7 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 129-137, 1991.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein