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

$$a_n=\cases{ {\textstyle{1\over 2}}a_{n-1} & for $a_{n-1}$\ even\cr 3a_{n-1}+1 & for $a_{n-1}$\ odd\cr}$$ (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

$$t_n=\cases{ {\textstyle{1\over 2}}t_{n-1} & for $t_{n-1}$\ ... ...r {\textstyle{1\over 2}}(3t_{n-1}+1) & for $t_{n-1}$\ odd\cr}$$ (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},$$ (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},$$ (4)

where

$$\eta = 1-H(\theta)=0.05004\ldots$$ (5)

$$H(x) = -x\lg x-(1-x)\lg(1-x)$$ (6)

$$\theta = {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).$$ (8)

Then

$$T(x)={m_ix-r_i\over d}$$ (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$$ (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

$$T_k(x)=\cases{ {\textstyle{1\over 2}}x & for $x\equiv 0\ \l... ...}(3x+k) & for $x\equiv 1\ \left({{\rm mod\ } {2}}\right)$,\cr}$$ (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

$$T(x)=\cases{ 7x+3 & for $x\equiv 0\ \left({{\rm mod\ } {3}}... ...3}}(x-2) & for $x\equiv 2\ \left({{\rm mod\ } {3}}\right)$\cr}$$ (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

References

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. http://www.cecm.sfu.ca/organics/papers/lagarias/.

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.'' http://www.maths.uq.oz.au/~krm/survey.ps. Rev. Mar. 30, 1999.

Matthews, K. R. ``A Generalized $3x+1$ Conjecture.'' [$100 Reward for a Proof.] ftp://www.maths.uq.edu.au/pub/krm/gnubc/challenge.

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.'' http://www.research.att.com/~njas/sequences/eisonline.html 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.