CollatzProblem 2001-08-19 10:20:17 2003-11-05 16:17:52 Conjecture Collatz Ulam \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} We define the function $f : \mathbb{N} \longrightarrow \mathbb{N} $ (where $\mathbb{N}$ excludes zero) such that $$ f(a) = \left\{ \begin{array}{rl} 3a+1 & \text{ if } a \text{ is odd } \\ a/2 & \text{ if } a \text{ is even.} \end{array} \right. $$ Then let the sequence $c_n$ be defined as $c_i = f(c_{i-1})$, with $c_0$ an arbitrary natural seed value. It is conjectured that the sequence $c_0, c_1, c_2, \ldots$ will always end in $1,4,2$, repeating infinitely. This has been verified by computer up to very large values of $c_0$, but is unproven in general. It is also not known whether this problem is decideable. This is generally called the \emph{Collatz problem}. The sequence $c_n$ is sometimes called the ``hailstone sequence''. This is because it behaves analogously to a hailstone in a cloud which falls by gravity and is tossed up again repeatedly. The sequence similarly ends in an eternal oscillation.