# Collatz Problem

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.