Collatz Problem

Define the following function on $\mathbb{N}$ : $f(n)=\begin{cases} 3n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}$ The Collatz conjecture says that, for any positive integer $n$ , the sequence $\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}$ contains 1. This conjecture is still open. Some people have described it as the easiest unsolved problem in mathematics.

Properties of $f(n)$

Self similarity of $f(n)$ follows from generalizing $n$ to an integral, integer coefficient polynomial. If $n=2^zx+b$ for example, it can be shown by parity argument, that $n$ has the same parity as $b$ . It then follows, that same conditional path will be followed by $n$ as it was for $b$ ; any time the lead coefficient still has a factor of 2.

Observing that if $n=2m+1$ then $3n+1=6m+4$ , as well as: ${6m+4\over 2}=3m+2$ we can then observe that; only if $m$ is even will another division by 2 be possible.

The above observation leads to 2 important points about $n=4c+3$ ; namely they are the only possible lowest elements of a non-trivial cycle, and also the only possible lowest elements of an infinitely increasing sequence.

Page

Toolbox

Search

Collatz Problem

Properties of $f(n)$